[Python] 백준 1240번 노드사이의 거리

문제

1240번: 노드사이의 거리

입력

• 첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N - 1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

• M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

입력 예제

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

출력 예제

2
7

문제 풀이

• 인접리스트로 그래프를 만든 후, 가중치 값을 더해가며 경로를 탐색한다.

코드

from collections import deque

def bfs(start, end):
    visited = [0] * (n + 1)
    queue = deque()
    queue.append((start, 0))
    visited[start] = 1
    while queue:
        now, cost = queue.popleft()
        if now == end:
            return cost
        for nn, c in graph[now]:
            if visited[nn] == 0:
                visited[nn] = 1
                queue.append((nn, cost + c))

n,m = map(int,input().split())
graph = [[] for _ in range(n + 1)]

# 그래프 입력받기
for _ in range(n - 1):
    u, v, w = map(int,input().split())
    graph[u].append((v,w))
    graph[v].append((u,w))
# print(*graph)
# m개의 노드 쌍 입력
for _ in range(m):
    start, end = map(int,input().split())
    print(bfs(start,end))