[BOJ] Python 택배(1719)

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

 

 

플로이드 워셜로 푸는 대표적인 문제이다.

거리 배열 외에도 정답배열을 통해 최단 경로시 가장 먼저 접근해야하는 노드의 값을 테이블로 만들어야 한다.

 

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
distance = [[float('inf')] * (N+1) for _ in range(N+1)]
graph = [[0] * (N+1) for _ in range(N+1)]


for _ in range(M):
    s,e,cost = map(int,input().split())

    if distance[s][e] > cost:
        distance[s][e] = cost
        graph[s][e] = e
    if distance[e][s] > cost:
        distance[e][s] = cost
        graph[e][s] = s

def floyid():
    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]

                    graph[i][j] = graph[i][k]



floyid()

for i in range(1,N+1):
    for j in range(1,N+1):
        if float('inf') <= distance[i][j] or i==j:
            print('-',end=' ')

        else:
            print(graph[i][j],end=' ')

    print()

 

dijkstra 풀이

 

import sys
import heapq
input = sys.stdin.readline

N,M = map(int,input().split())
distance = [[float('inf')] * (N+1) for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
result = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    s,e,cost = map(int,input().split())
    graph[s].append((e,cost))
    graph[e].append((s,cost))
    result[s][e] = e
    result[e][s] = s

def dijkstra(start):
    hq = []
    distance[start][start] = 0

    heapq.heappush(hq,(0,start))

    while hq:
        dist, now_node = heapq.heappop(hq)
        if distance[start][now_node] > dist:
            continue
        for next_node, cost in graph[now_node]:
            if distance[start][next_node] > dist + cost:
                distance[start][next_node] = dist + cost
                if now_node == start:
                    result[start][next_node] = next_node
                else:
                    result[start][next_node] = result[start][now_node]
                heapq.heappush(hq,(dist+cost, next_node))


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

for i in range(1,N+1):
    for j in range(1,N+1):
        if i == j:
            print('-',end=' ')
        else:
            print(result[i][j], end= ' ')
    print()

 

회고.

가장 먼저 접근해야하는 노드 테이블을 갱신할 때, 노드 테이블을 참조해서 갱신( graph[i][j] = graph[i][k] )해야하는데

(graph[i][j] = k) k값을 그냥 때려박는 발상으로 좀 헤맷던 것 같다..