[파이썬] 백준 1240 : 노드 사이의 거리 (골드5)

[파이썬] 백준 1240 : 노드 사이의 거리 (골드5)

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

---

풀이

방향성 생각

• 입력이 작아서 $N^2$로도 풀리는 기본 문제
• 노드마다 BFS를 돌려서 거리를 구한다.
• 큐에 노드와 거리를 같이 전달해서 V를 boolean으로 설정하거나, visit에 거리를 저장해서 이전 노드에서 불러온다.

---

전체코드

from collections import deque

# node X에서 BFS를 돌려서 얻은 거리 리스트 반환
def bfs(x: int) -> list:

    V = [-1]*(N+1)
    V[x] = 0

    Q = deque([x])
    while Q:
        x = Q.popleft()

        for nx,cost in G[x]:
            if V[nx] == -1:
                V[nx] = V[x] + cost
                Q.append(nx)
    return V

N,M = map(int,input().split())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))
    G[b].append((a,cost))

dist = {i:bfs(i) for i in range(1,N+1)}

# 주어진 쿼리에서 미리 구한 dist 결과 출력
question = [tuple(map(int,input().split())) for _ in range(M)]
for start,end in question:
    print(dist[start][end])

코멘트

• 시간이 좀 더 빡빡한 문제였으면, 쿼리에서 시작 또는 끝 노드를 먼저 구하고 중복제거 후 필요한 노드만 돌렸을 듯.