[백준/python] 1719번 택배

1719번: 택배 (acmicpc.net)

코드

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10**6)

import heapq

# 노드200, 경로10000

n, m = map(int, input().split())

 

INF = int(1e9)

graph = [[] for _ in range(n+1)]

# 간선 정보 입력

for _ in range(m):

    a, b, c = map(int, input().split())

    # a<->b가 c비용

    graph[a].append((b, c))

    graph[b].append((a,c))

def find(target):

   

    if target == ans[target]:

        return target

    ans[target]=find(ans[target])

    return ans[target]

def dijkstra(ans, start):

    distance = [INF] * (n+1)

    q = []

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

    distance[start] = 0

    ans[start] = start # 자기자신으로 갈때 가장 짧은길 -

    while q:

        dist, now = heapq.heappop(q)

        if distance[now] < dist:

            continue

        for i in graph[now]:

            cost = dist + i[1]

            if cost < distance[i[0]]:

                distance[i[0]] = cost

                heapq.heappush(q, (cost, i[0]))

                ans[i[0]] = now

    for i in range(n): # 자기 부모 타고타고 최종 부모

        if ans[i+1] == start:

            ans[i+1] = i+1

    for i in range(n):        

        ans[i+1] = find(i+1)                

    return ans

ans_gragh = [] # 이따 하나씩 채우자

# 다익스트라 알고리즘을 수행

for k in range(n):

    ans = [[] for _ in range(n+1)] # 자기 최종부모 저장

    '''자기 앞 부모 저장하는 시점. 여기가 가장 짧은 거리임을 확인한 순간.

    '''

    ans_gragh.append(dijkstra(ans, k+1))

   

# 다익스트라 한번 돌면 그 노드에 대해 모든 노드로가기위한 최단거리가 저장됨.

''' 내가 필요한건 걔네들이 맨 처음 간 노드

그냥 자기 앞 노드 저장. 타고타고 올라가서 한방향트리의 부모노드 찾기마냥...

union-find를 쓰는게 빠를까 나쁠까

'''

for i in range(n):

    for j in range(n):

        if j == i:

            print('-',end=' ')

        else:

            print(ans_gragh[i][j+1],end=' ')

    print()

풀이

다익스트라+union-find를 사용하여 풀었다.

다익스트라를 사용하여 각 노드들에서 출발할 때 각 노드들에 대해 가장 짧은 거리를 구하고, 그때마다 어디서 온 노드인지를 ans에 저장하였다. 그다음 start에서 온 길이라면 자기 자신을 입력하고 find 함수를 통해 자기 앞 노드를 찾아낸다.

해당 알고리즘을 사용하는게 효율적인지 아닌지는 더 공부해봐야겠다.