(Python) - BOJ(1240번) : 노드사이의 거리

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

1240번: 노드사이의 거리

---

• 해설 : 

N개의 노드로 이루어진 트리가 주어지고, 노드 사이의 거리 M개가 주어질 때, testCase에 대해 노드 사이의 거리를 출력하는 문제이다.

 

 

 

---

• 풀이 :

양방향 연결이므로 노드 사이의 거리와 연결 정보를 0번노드부터 N-1번 노드까지 가공한 후 이를 BFS로 탐색하며 원하는 노드가 나왔을 때 거리를 출력한다.

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
 
def bfs(start,end):
 
    queue = deque([start])
    length = [-1 for _ in range(n+1)]
    length[start] = 0
    while queue:
        s = queue.popleft()
        for e,w in tree[s]:
            if length[e] == -1:
                queue.append(e)
                length[e] = max(length[s] + w,length[e])
    return length[end]
 
 
if __name__ == "__main__":
    n,m = map(int,sys.stdin.readline().split())
    tree = [[] for _ in range(n+1)]
    for _ in range(n-1):
        s,e,w = map(int,input().split())
        tree[s].append([e,w])
        tree[e].append([s,w])
    for _ in range(m):
        start,end = map(int,input().split())
        print(bfs(start,end))