백준 1240번 노드 사이의 거리 파이썬 풀이

정답 코드

#BOJ 1240 
#2022 06 17 05:56~
import sys
from collections import deque
input = sys.stdin.readline
def main():
    n, m  = map(int,input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        v1, v2, d = map(int,input().split())
        graph[v1].append((d,v2))
        graph[v2].append((d,v1))
 
    ans = []
    for _ in range(m):
        v1, v2 = map(int,input().split())
        cur=v1
        distance=0
        q = deque()
        q.append((0,v1))
        visited = [False]*(n+1)
        visited[v1]=True
        while q:
            d, v = q.popleft()
            if v == v2:
                distance=d
                break
            for l, i in graph[v]:
                if not visited[i]:
                    visited[i]=True
                    q.append((d+l,i))
        ans.append(distance)
    print('\n'.join(list(map(str,ans))))
    return
main()

핵심 정리

1. 큐에는 "현재" 에 해당하는 정보를 모두 저장할 수 있다. 정점 뿐만 아니라, 현재까지 지나온 거리도 튜플로 저장할 수가 있는 것이다.