99클럽 코테 스터디 7일차 TIL - 노드 사이의 거리(백준 #1240)

❇️오늘의 학습 키워드 : 노드 사이의 거리(백준 #1240)

 

문제

 N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

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

출력

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

제한

•  2≤N≤1000
•  1≤M≤1000
• 트리 상에 연결된 두 점과 거리는 10000이하인 자연수이다.
• 트리 노드의 번호는 1부터 N까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다.

예제 입력 1 

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

예제 출력 1 

2
7

정답 코드

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

N, M = map(int,input().split())
arr = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b,dist = map(int,input().split())
    arr[a].append((b, dist))
    arr[b].append((a, dist)) # 무방향이므로 양쪽으로 연결

def bfs(start, end):
    q = deque([(start, 0)])
    visited = [0] * (N + 1)
    visited[start] = 1

    while q:
        node, total_dist = q.popleft()

        if node == end:
            return total_dist

        for nxt, dist in arr[node]:
            if visited[nxt] == 0:
                visited[nxt] = 1
                q.append((nxt, total_dist + dist))

for _ in range(M):
    a, b = map(int, input().split())
    print(bfs(a,b))

❇️오늘의 회고

  - 노드 사이의 관계(거리)를 묻는 문제이므로 바로 BFS를 떠올릴 수 있었다!

  - 무방향이므로 양쪽으로 연결하는 것도 잊지 말아야한다.

  - 내일 11시, 문제를 풀기 전에 위 개념을 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 공부할 것이다!🙂