[BOJ/Python] 1240. 노드사이의 거리

📌 문제

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

1240번: 노드사이의 거리

 

📌 문제 접근 방법

1. 인접 행렬을 만들고 노드 간 연결이 된 곳에 거리를 저장!
   → 시간 초과
2. 인접 리스트로 바꾸고 리스트에 연결된 노드번호와 거리를 함께 저장 후 bfs로 탐색
3. 인접 행렬로 그래프 탐색을 하는 경우 시간 초과가 될 때가 종종 있어서 인접 리스트를 우선적으로 쓰는 것이 좋을 것 같다!

 

📌 코드

from collections import deque

def distance(x, y):
    queue = deque()
    queue.append((x, 0))

    visited = [0 for _ in range(N+1)]
    visited[x] = 1

    while queue:
        v, d = queue.popleft()

        if v == y:
            return d

        for w, dist in graph[v]:
            if not visited[w]:
                visited[w] = 1
                queue.append((w, d+dist))


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

for _ in range(N-1):
    i, j, dist = map(int, input().split())

    graph[i].append((j, dist))
    graph[j].append((i, dist))

for _ in range(M):
    x, y = map(int, input().split())
    print(distance(x, y))