[파이썬] 백준 9694 : 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (골드3)

[파이썬] 백준 9694 : 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (골드3)

 

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

---

 

문제

---

풀이

0.방향성 생각

node A부터 node B까지 가는 최소 비용과 최소 경로를 구하는 문제. 최소 비용은 다익스트라로 풀 수 있다.

1. 다익스트라 함수 정의

import heapq
import sys
input = sys.stdin.readline

def dijkstra(graph,start):

    global node
    dist = [float('inf')]*node
    dist[start] = 0 # 시작 노드 거리 0
    q = [(0,start)] # (weight,node)
    path = [-1]*node # 역추적

    while q:
        x_dist,x_node = heapq.heappop(q) # 시작점까지 거리, 현재 노드

        if x_dist > dist[x_node]: # 시작점 까지 거리 크면 패스
            continue

        for nx_node,weight in graph[x_node]: # 그렇지 않은 경우
            nx_dist = x_dist + weight # nx까지 거리 = x까지 거리+ 가중치

            if nx_dist < dist[nx_node]: # 새로운 경로가 이득이면 업데이트
                dist[nx_node] = nx_dist # 다음 노드까지 걸리는 비용
                path[nx_node] = x_node # 어디서 왔는지 업데이트
                heapq.heappush(q,(nx_dist,nx_node)) 
    return dist,path

dist는 처음에 그래프에서 만들 수 없는 큰 수로 초기화 시켜준다.
시작점 start에서 시작하므로 start의 거리를 0으로 초기화 시켜준다.
힙에 (거리,출발 노드)를 넣는다.
path에는 역추적을 해야하므로 일단 -1로 초기화 시켜놓는다.

while문 내부에서 큐를 돌린다.
처음에는 시작점을 제외한 모든 부분이 inf로 초기화 돼어있다.
for문 내부로 내려가서 시작점과 연결된 부분들에 대해서 탐색한다.
다음 노드로 가는 비용을 nx_dist로 정의한다. 이게 다음 노드인 nx_node까지 비용보다 작다면 dist를 업데이트 하고 path에도 경로를 찾기위해 어떤 노드에서 왔는지(x_node) 추가한다. 큐에다가 같은 방식으로 또 추가해준다.

2. 출력

t = int(input())

for case in range(t):
    edge,node = map(int,input().split())
    graph = [[] for _ in range(node)]

    for _ in range(edge):
        x,y,weight = map(int,input().split())
        graph[y].append((x,weight))
        graph[x].append((y,weight))

    d,trace = dijkstra(graph,0)
    cost = d[-1]

    if cost == float('inf'):
        print(f'Case #{case+1}: -1')

    else:
        answer = []
        node = node-1 
        while node != -1:
            answer.append(node)
            node = trace[node]

        print(f'Case #{case+1}:',*answer[::-1])

무방향 그래프이므로 양쪽 모두에 추가한다. 추가할 때 가중치도 같이 추가한다.

함수의 리턴값은 거리 리스트 d와 경로가 포함된 trace를 얻는다.

마지막까지 도달하지 못하면 d의 맨 뒷부분이 inf로 그대로이다. 이 때는 -1를 출력하게 해준다.

그렇지 않는 경우 answer를 정의하고 trace에서 순서대로 역추적한다.
테스트 케이스 1 같은 경우에는 [-1, 0, 0, 2, 2] 이런식으로 trace가 구성되어있다.
마지막 인덱스에 2가 저장돼어 있으므로 2번 인덱스로 이동한다. 2번 인덱스에는 0이 저장돼있으므로 0으로 이동한다.
인덱스 0에는 -1, 시작점이 저장돼있으므로 멈춘다. 이러면 4 -> 2 -> 0 순서로 이동했고 이를 뒤집어주면 경로가 나온다.

---

전체코드

import heapq
import sys
input = sys.stdin.readline

def dijkstra(graph,start):

    global node
    dist = [float('inf')]*node
    dist[start] = 0 # 시작 노드 거리 0
    q = [(0,start)] # (weight,node)
    path = [-1]*node # 역추적

    while q:
        x_dist,x_node = heapq.heappop(q) # 시작점까지 거리, 현재 노드

        if x_dist > dist[x_node]: # 시작점 까지 거리 크면 패스
            continue

        for nx_node,weight in graph[x_node]: # 그렇지 않은 경우
            nx_dist = x_dist + weight # nx까지 거리 = x까지 거리+ 가중치

            if nx_dist < dist[nx_node]: # 새로운 경로가 이득이면 업데이트
                dist[nx_node] = nx_dist # 다음 노드까지 걸리는 비용
                path[nx_node] = x_node # 어디서 왔는지 업데이트
                heapq.heappush(q,(nx_dist,nx_node)) 
    return dist,path

t = int(input())

for case in range(t):
    edge,node = map(int,input().split())
    graph = [[] for _ in range(node)]

    for _ in range(edge):
        x,y,weight = map(int,input().split())
        graph[y].append((x,weight))
        graph[x].append((y,weight))

    d,trace = dijkstra(graph,0)
    cost = d[-1]

    if cost == float('inf'):
        print(f'Case #{case+1}: -1')

    else:
        answer = []
        node = node-1 
        while node != -1:
            answer.append(node)
            node = trace[node]

        print(f'Case #{case+1}:',*answer[::-1])

코멘트

역추적 하는 부분은 숨바꼭질 시리즈같은 BFS 문제에서도 했었던거라 다익스트라 구현만 하면 어렵지 않게 풀 수 있다.