99클럽 코테 스터디 7일차 TIL + DFS, Tree

문제

Baekjoon1240: 노드사이의 거리

• 설명: 트리가 주어지고 두 노드가 주어지면 두 노드 사이의 거리를 출력하여라

풀이

• 트리의 특징인 두 노드 사이의 경로는 유일하다는 점을 이용한다.
  • 만약 그래프였다면 두 노드 사이의 최단 경로라든지, 최장 경로라든지 답이 유일하게 나오도록 문제를 만들어야한다.
  • 하지만 이 문제는 트리이기 때문에 두 노드 사이의 (최단 경로) = (최장 경로) = (유일한 경로) 이다.
• DFS, BFS를 통해 두 노드 사이의 거리를 구해준다.
• 플로이드 와샬 알고리즘처럼 미리 모든 노드 쌍의 거리를 구해주어도 되지만 쿼리가 $1,000$개 밖에 들어오지 않기 때문에 매번 계산해주어도 된다.

시간 복잡도

• $O(nm)$
• 두 노드 사이의 거리 구하기: $O(n)$
• $m$번의 쿼리: $O(m)$

오늘의 회고

• 2달 전에 풀었던 문제였는데 그때랑 지금이랑 달라진건 변수명 밖에 없다 ㄷㄷ 쉽게 변하지 않나보다

Code

# Baekjoon01240.py
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

adj_list = [ [] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    adj_list[a].append((b, c))
    adj_list[b].append((a, c))

def dfs(me, mom, target):
    if me == target:
        return 0

    for adj, cost in adj_list[me]:
        if adj != mom:
            result = dfs(adj, me, target)
            if result != -1:
                return result + cost

    return -1

for _ in range(m):
    a, b = map(int, input().split())

    print(dfs(a, 0, b))