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

 

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

1240번: 노드사이의 거리

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

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

예제 입력 1 복사

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력 1 복사

2
7

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

 

풀이: 트리 구조는 여러 노드가 한 노드를 가리킬 수 없는 구조라는 것만 기억하자. 

bfs 탐색을 위해 각 간선간의 관계를 선언 후, 

bfs를 수행하면 된다. 

약간의 trick은 visit 을 -1로 초기화 하고, 노드에서 다음 노드로 건너갈 때 weight를 더해준다. 

첫 노드의 weight는 0으로 선언한다. (-1은 방문 안한 노드, 0으로 설정해야 weight더했을 때 문제 X)

 

visit 을 선언 할 때 visit = [0]*n 으로 선언하고 1 부터 시작하는 graph시 indexing을 위해 n-1 형태로 접근 했는데 

오늘부터 고집을 꺾고 visit = [0] * (n+1) 선언하기로 한다. 

 

이 문제는 LCA 로 해결이 가능하다고 한다. 

시간 복잡도를 많이 단축할 수 있다고 하는데, 아직 BFS 도 바로 바로 잘 안되는 나로써는 좀 더 시간을 갖고 나중에 도전해보도록 한다. 

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

n,m = map(int, input().split())
#트리는 여러 노드가 한 노드를 가리킬 수 없는 구조 

data = [[] for _ in range(n+1)]
q = deque()

def bfs(s,e):
    q.append(s)
    visited = [-1] * (n+1)
    visited[s] = 0
    while q:
        tmp = q.popleft()
        for node, d in data[tmp]:
            if visited[node] != -1:
                continue
            visited[node] = visited[tmp] + d
            if node == e:
                q.clear()
                return visited[e]
            else:
                q.append(node)
    return visited[e]


for _ in range(n-1):
    _s, _e, _d = map(int, input().split())
    data[_s].append((_e, _d))
    data[_e].append((_s,_d))

for _ in range(m):
    s,e = map(int, input().split())
    print(bfs(s,e))