[99클럽/파이썬 챌린저/7일차] 노드 사이의 거리

백준 1240번 노드 사이의 거리 G5

 

문제
N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.
입력 첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N−1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

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

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

 

 

그래프 이론, 그래프 탐색, 트리, bfs, dfs

 

트리의 각 노드 사이의 거리를 찾는 문제가 나왔다.

bfs + dp로 풀이하였다.

 

 

모든 정점에서 모든 정점까지의 거리를 미리 구하고 답만 출력하는 방식을 택하였다.

문제 제한인 N과 M이 매우 작아서 미리 구해둬도 문제가 없어 보이기 때문이다.

 

트리에서는 두 정점 사이의 경로는 유일하다는 특징이 있다.

이를 이용하여 bfs를 한 번만 돌리고 구하려 했으나 방법이 생각나지 않아, 모든 정점에서 bfs를 돌렸다.

 

 

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

routes = [[] for _ in range(n+1)]

for _ in range(n-1):
    v1, v2, c = map(int, sys.stdin.readline().split())
    routes[v1].append((v2, c))
    routes[v2].append((v1, c))
dp = [[0] * (n+1) for _ in range(n+1)]


visit = [False] * (n+1)
def bfs(i):
    visit = [False] * (n+1)
    visit[i] = True
    dq = deque()
    dq.append([i,0])
    while dq:
        v, d = dq.popleft()
        for vv, c in routes[v]:
            if visit[vv]: continue
            visit[vv] = True
            dq.append((vv, c+d))
            dp[i][vv] = c+d
            dp[vv][i] = c+d
            
for i in range(1, n+1):
    bfs(i)

for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    print(dp[s][e])

 

 

---

 

이후 코드 개선은 했으나, 근본적인 로직의 문제는 벗어날 수 없어 보인다. 이후에 다시 풀 예정이다.