[Python] 노드사이의 거리 - 백준 (BFS)

해당 글은 백준 1240번 문제 '노드사이의 거리'을 다룬다.

문제

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

1240번: 노드사이의 거리

 

설명

해당 문제는 그래프로 모든 노드에 대한 거리값을 저장해두고, 두 노드 사이의 거리를 구할 때 BFS 를 사용하여 해결할 수 있다.

 

코드

from collections import deque
import sys
input = sys.stdin.readline

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

def bfs(n1, n2):
    q = deque()
    q.append((n1, 0))
    visited = [False]*(n+1)
    visited[n1] = True
    while q:
        cur_n, cur_dist = q.popleft()
        if cur_n == n2:
            return cur_dist
        for (next_n, next_dist) in graph[cur_n]:
            if not visited[next_n]:
                visited[next_n] = True
                q.append((next_n, cur_dist+next_dist))

for _ in range(n-1):
    n1, n2, dist = map(int, input().split())
    graph[n1].append((n2, dist))
    graph[n2].append((n1, dist))

for _ in range(m):
    n1, n2 = map(int, input().split())
    print(bfs(n1, n2))