백준 1240 노드사이의 거리 파이썬 풀이

난이도 : 골드5

풀이일 : 2403273

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

1240번: 노드사이의 거리

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys
from collections import deque


def sol(n, m):
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        for nx, add in tree[x]:
            if nx == m:  # 도착했다면 거리 출력 반환
                return print(visited[x] + add)
            if not visited[nx]:  # 도착하지 못했다면 이동 기록
                visited[nx] = visited[x] + add
                queue.append(nx)
    return


N, M = list(map(int, sys.stdin.readline().split()))
tree = [[] for _ in range(N + 1)]  # 연결 정보 저장

for _ in range(N - 1):  # 양방향 연결 정보, 거리 기록
    u, v, c = list(map(int, sys.stdin.readline().split()))
    tree[u].append([v, c])
    tree[v].append([u, c])

for _ in range(M):  # 거리 구하기
    visited = [0] * (N + 1)  # 출발 노드부터의 거리
    s, e = list(map(int, sys.stdin.readline().split()))
    sol(s, e)

• BFS 방식으로 출발 노드부터 도착노드까지의 거리를 구해 출력하였다.
• tree : 2차원 배열로 만들어 연결 정보와 거리를 기록하였다. 이 때, 연결 정보는 양방향으로 저장해준다.
• visited : 출발노드부터의 거리를 저장하기 위한 배열이다. 도착 노드까지 직접 도착할 수 없는 경우에는 각 노드간 이동 거리를 합산해 기록한다.
• 한 노드에서 다른 노드까지 이동하는 경로가 여러 개 존재하는 문제가 아니었기 때문에, heapq를 이용한 최소비용으로 접근하지 않고 BFS 방식으로 풀이하였다.

---

느낀점

• 한동안 엄청 풀었었던 문젠데, 당시에는 지금보다 빨리 풀었을 것 같지만 오래 풀지 않으니 조금 잊어버린 느낌이다. 풀었던 문제들을 다시 풀어봐야 할까 싶다.