[백준1719] / 택배 - 다익스트라

 

백준1719

 

 

푼 날짜 : 2024.11.12

푼 문제 : [1719] / 택배

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

행렬로 계산하는 거라 처음에는 당황했지만 인덱스 계산만 잘하면 된다!

인덱스 계산 외에는 일반적인 다익스트라와 동일하다. 

대신 이전 위치를 함께 저장해야 하므로 나는 튜플로 저장했다.

 

스페셜 저지 문제이므로 예제 출력과 다르게 나와도 맞는 경우의 수라면 정답처리 된다.

(이런 문구가 없어서 처음에 고민했지만 걱정말고 제출해도 된다!)

 

[ 예제 출력 ]

- 2 3 3 2 2
1 - 1 4 5 5
1 1 - 4 5 6
3 2 3 - 6 6
2 2 3 6 - 6
5 5 3 4 5 -

 

[ 내가 제출한 코드의 출력 ]

- 2 3 3 2 2 
1 - 1 4 5 5 
1 1 - 4 1 6 
3 2 3 - 6 6 
2 2 2 6 - 6 
5 5 3 4 5 -

 

 

3 -> 5 로 이동할 때

빨간 경로처럼 3-1-2-5 로 갈 수도 있고

파란 경로처럼 3-5 로 갈 수도 있다.

 

=> 둘 다 비용은 6으로 동일하기 때문에 둘 다 정답처리 된다!

 

(내)이해를 돕기 위한 이미지

 

 

 

 

코드 :

import sys
import heapq

N, M = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

# 어느 집하장에서 왔는지, 가중치(이동에 걸리는 시간)
dist = [[(-1, float('INF')) for _ in range(N+1)] for _ in range(N+1)]

def dijkstra(i, j):
    heap = [(0, i, j)]
    dist[i][j] = (0, 0)

    while heap:
        now_cost, now_y, now_x = heapq.heappop(heap)

        if dist[now_y][now_x][1] < now_cost: continue

        for next_x, cost in graph[now_y]:
            all_cost = now_cost + cost

            if dist[next_x][now_x][1] > all_cost:
                dist[next_x][now_x] = (now_y, all_cost) # (어디서 왔는지, 가중치)
                heapq.heappush(heap, (all_cost, now_x, next_x))

# 각 집하장마다 거리 계산해주기
for i in range(1, N+1): dijkstra(i, i)

# 출력 (어디서 왔는지 출력하면 되므로 0 번째 인덱스 출력)
for i in range(1, N+1):
    for j in range(1, N+1):
        print(dist[i][j][0] if i != j else '-', end=' ')
    print()
print()

 

 

 

차분하게 차근차근 풀어나가면 해결할 수 있다 :)