[백준 1719] 택배

🍎 [백준 1719] 택배

문제링크

https://www.acmicpc.net/problem/1719

1719번: 택배

 

 

⚾ 코드

- 다익스트라

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

N, M = map(int, input().split())

result = [[0]*(N+1) for _ in range(N+1)]  # 결과 테이블
graph = [[] for _ in range(N+1)]


for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))  # 양방향
    graph[b].append((a, c))


def dijkstra(start):
    q = []
    # 시작 노드 초기화
    heapq.heappush(q, (0, start))
    distance = [[INF, 0] for _ in range(N+1)]
    distance[start] = [0, 0]
    result[start][start] = "-"

    for i in graph[start]:
        # 시작노드에서 처음 도착하는 노드 초기화
        next_node = i[0]
        next_node_cost = i[1]

        distance[next_node] = [next_node_cost, next_node]
        heapq.heappush(q, (next_node_cost, next_node))
        result[start][next_node] = next_node

    while q:
        dist, now = heapq.heappop(q)

        for i in graph[now]:
            next_node = i[0]
            next_node_cost = i[1]

            cost = distance[now][0]+next_node_cost

            if distance[next_node][0] <= dist:  # 이미 방문한 노드는 continue
                continue

            if distance[next_node][0] > cost:
                # 최단 거리 갱신
                # distance[next_node] 에는 [거리, 이전 노드에 오기까지 가장 먼저 도달한 노드]
                distance[next_node] = [cost, distance[now][1]]
                heapq.heappush(q, (cost, next_node))
                result[start][next_node] = distance[now][1]


for i in range(1, N+1):
    dijkstra(i)

for i in range(1, N+1):
    print(' '.join(map(str, result[i][1:])))

 

- 플로이드 워셜

# 플로이드 워셜
import sys
input = sys.stdin.readline
INF = int(1e9)

N, M = map(int, input().split())

distance = [[INF]*(N+1) for _ in range(N+1)]
result = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    distance[a][b] = c
    distance[b][a] = c
    result[a][b] = b
    result[b][a] = a


for i in range(1, N+1):
    distance[i][i] = 0
    result[i][i] = "-"

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):

            if distance[i][j] > distance[i][k]+distance[k][j]:
                distance[i][j] = distance[i][k]+distance[k][j]
                result[i][j] = result[i][k]

for i in range(1, N+1):
    print(' '.join(map(str, result[i][1:])))

 

🔔 해결 과정 & 깨달은 점

- 처음에 그냥 단순하게 모든 노드에서 모든 노드에 대한 정보를 구해야 하니까 플로이드 워셜 알고리즘으로 풀어야지! 라고 생각하며 풀었는데, 다익스트라로도 풀 수 있을 것 같아서 방향을 바꿨다.

- 풀이 과정은 다음과 같다.

 

아래의 그림은 1번 노드에서 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 구하는 과정이다.

0. 다익스트라 알고리즘을 기반으로 하며,

distance 테이블은 [최단거리, 첫번째로 도달한 노드]로 구성되어 있다.

 

1. 먼저 기준 노드에서 첫 번째로 도달하는 노드를 초기화 해야 한다.(파란색 글씨)

이렇게 해야 다음 노드를 방문 할 때 그 경로가 어디에서 시작된 노드인 지 알 수 있다.

 

2. heapq에서 하나씩 노드(이 노드를 now라고 할 것이다.)를 꺼내면서 탐색을 한다.

이때, 최단거리가 갱신이 되면, distance[1]을 distance[now][1] 과 같은 값으로 갱신한다.

이 때 result 테이블도 갱신한다.

result 테이블은 [기준노드][next_node] = distance[now][1] 의 값이 들어가게 된다.

 

 

 

3. heapq에 아무것도 들어있지 않을 때 까지 반복한다.

 

4. heapq에 아무것도 들어 있지 않게 되면 while 문을 빠져 나오게 되고 아래 그림과 같은 결과가 나온다.

result테이블은 [기준노드][next_node]의 값을 갱신했기 때문에 한 행씩 update 된다. 

 

---

추가

 

플로이드 워셜 알고리즘으로도 역시 풀 수 있었다.

result의 값을 갱신해줄 때 result=[i][j]가 아닌 result=[i][k] 로 바꾸어주니 바로 해결 되었다.