알고리즘 - Python / 백준 - 1240번 : 노드사이의 거리

1240번: 노드사이의 거리 (acmicpc.net)

1240번: 노드사이의 거리

 

---

풀이

• 트리에서 노드 사이의 거리를 입력받고 입력된 두개의 노드 사이의 거리를 출력하는 문제이다.
• bfs를 통해 트리를 탐색하고 way 배열에 start 노드 부터 해당 노드까지의 거리를 저장하였다.
• bfs의 큐에서 end 노드가 pop 되는 시점이 목표 노드까지 도달하였다는 뜻이므로 , way 배열에 저장된 해당 노드까지의 거리를 출력하면 된다.

 

import sys
n,m = map(int, sys.stdin.readline().split(" "))
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
    a,b,c = map(int, sys.stdin.readline().split(" "))
    graph[a].append([b,c])
    graph[b].append([a,c])

def bfs(start,end):
    root = [start]
    global n
    global graph
    visited = [0]*(n+1)
    way = [0]*(n+1)
    while root:
        k = root.pop(0)
        if k == end:
            break
        if visited[k] == 0:
            visited[k] = 1
            for i in graph[k]:
                root.append(i[0])
                way[i[0]] = way[k] + i[1]
    return way[end]

for _ in range(m):
    a,b = map(int, sys.stdin.readline().split(" "))
    print(bfs(a,b))

---