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

💡문제접근

• 여태까지 풀었던 그래프 이론 문제는 가중치가 없었는데 이 문제는 각 노드 사이의 가중치가 주어지는 형태의 다른 문제였다.
• 가중치가 주어지는 형태의 문제는 각 노드 사이의 관계를 표현할 때 튜플 형태로 묶어서 가중치도 같이 넣어주면 해결할 수 있다.

💡코드(메모리 : 34176KB, 시간 : 204ms)

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

N, M = map(int, input().strip().split())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().strip().split())
    # 가중치가 있는 트리 구조이므로 튜플 형태로 가중치 값도 같이 넣어준다.
    graph[u].append((v, w))
    graph[v].append((u, w))

def BFS(start, find):
    queue = deque()
    queue.append((start, 0))
    visited = [False] * (N + 1)
    visited[start] = True
    while queue:
        v, d = queue.popleft()
        if v == find:
            return d
        for i, w in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append((i, d+w))

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

💡소요시간 : 31m