[파이썬/python] 백준 - 1240 노드 사이의 거리

문제

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

---

문제 설명

1. N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받는다.
2. 두 노드 사이의 거리를 구하여라.

 

---

풀이

어렵지 않게 BFS 탐색 알고리즘을 사용하여 풀이했다.

 

문제에서 주어지는 노드 간 정보를 통해서 그래프를 생성한다. 이때 주어진 거리 정보도 그래프에 함께 저장한다.

그래프 생성 후 M개의 노드 쌍이 입력되면, start 위치에서 BFS 탐색을 진행하고 end위치에 도달했을 때 dist를 반환 후 출력한다.

 

정말 전형적인 BFS문제이기 때문에 그래프 탐색 문제를 많이 풀어봤다면 쉽게 풀 수 있는 문제였다.

---

코드

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

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

graph = [[] for _ in range(N+1)]

for i in range(N-1):
    v1,v2,c = map(int,input().split())
    graph[v1].append((v2,c))
    graph[v2].append((v1,c))

def bfs(s,e):
    queue = deque([(s,0)])
    visited = [0 for _ in range(N+1)]
    visited[s] = 1

    while queue:
        v1,c1 = queue.popleft()

        if v1 == e:
            return c1

        for v2,c2 in graph[v1]:
            if visited[v2]:
                continue

            queue.append((v2,c1+c2))
            visited[v2] = 1


for i in range(M):
    v1,v2 = map(int,input().split())
    print(bfs(v1,v2))

---

시간복잡도

• 인접 그래프에서 BFS의 시간복잡도는 $O(V+E)$이다.
• 최악의 경우 V = 1000, E = 약 1000, 횟수 M = 1000 이므로 약 $O(2*10^5)$정도의 시간복잡도는 가진다.