Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

1240. 노드사이의 거리

(골드 V) N개의 노드로 이루어진 트리가 주어질 때, M개의 노드 쌍의 거리를 각각 구하는 문제.

문제 링크: https://boj.kr/1240

1. 플로이드 워셜? (X)

처음 문제를 읽어보고는 단순 최단경로 문제인줄 알았다. 곧바로 플로이드-워셜 알고리즘을 작성하여 풀이를 시도해보았으나 바로 시간초과를 받았다. $n=1000$ 에서 $O(N^3)$ 알고리즘은 너무 큰 욕심이었나보다.

다음은 플로이드-워셜로 풀이를 시도할 때의 코드이다.

import sys


INF = 10001
MAX_N_NODES = 1000

dist = [[INF for x in range(MAX_N_NODES+1)] for y in range(MAX_N_NODES+1)]

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

for i in range(n-1):
    u, v, d = map(int, sys.stdin.readline().split())
    dist[u][v] = d
    dist[v][u] = d

## Floyd-Warshall
for k in range(1, MAX_N_NODES+1):
    for i in range(1, MAX_N_NODES+1):
        for j in range(1, MAX_N_NODES+1):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    sys.stdout.write(f'{dist[u][v]}\n')

2. Breadth-First-Search (O)

결국 새로운 코드를 작성하였고, “맞았습니다”를 받을 수 있었다. 새로운 접근법을 찾기위해서는 문제에서 ‘트리’라고 한 것에 주목해볼 필요가 있었다.

[위키백과] 트리는 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

어떤 노드에서 다른 노드로 갈 수 있는 길이 하나 밖에 없다면 최단 거리를 검색할 필요가 없어진다. 어차피 경로가 없지 않은 한, 어떠한 경우에도 경로는 하나 뿐일테니까.

따라서 DFS 혹은 BFS를 이용한 탐색 알고리즘을 구현해보았다. 코드는 아래와 같다.

import sys
from collections import defaultdict, deque
from typing import Deque, Dict, Set, Tuple


# graph[u][v] 는 u <-> v 사이 거리

dist: Dict[int, Dict[int, int]] = defaultdict(dict)


def bfs(src: int, dst: int) -> int:
    visited: Set[int] = set()
    queue: Deque[Tuple[int, int]] = deque()

    queue.append((src, 0))

    while queue:
        node, total_dist = queue.popleft()
        if node == dst:
            return total_dist
        if node not in visited:
            visited.add(node)
            for child, child_dist in dist[node].items():
                queue.append((child, total_dist + child_dist))

    raise ValueError


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

for i in range(n-1):
    u, v, d = map(int, sys.stdin.readline().split())
    dist[u][v] = d
    dist[v][u] = d

for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    sys.stdout.write(f'{bfs(u, v)}\n')

3. 알게 된 점.

  • 트리에서는 회로가 존재하지 않는다. (순환 경로가 없다.)
  • Floyd-Warshall 은 굉장히 느린 알고리즘이다.

Back to top