[Python] 백준 - 1967번&1167번 트리의 지름(DFS/BFS)

◈ 오류 정정 및 피드백 환영

1967번: 트리의 지름

---

1167번: 트리의 지름

---

🔎문제 분석

입력 형태만 다를 뿐 둘 다 동일한 문제이므로 1167번 예제를 기준으로 살펴보자면 트리는 다음과 같이 그려진다.

어떤 한 노드에서 가장 멀리 떨어진 노드 사이의 거리를 구해야 하므로 트리 탐색 문제이며, DFS 또는 BFS로 접근하면 된다.

 

하지만 노드 탐색 1번만으로는 트리의 지름을 구할 수 없다. 예컨데 아래 그림 속 3번째 예시 속 노드 3은 2번째 예시 속 노드 1과 달리 말단 노드가 아니기 때문에 트리의 지름보다 짧은 거리만을 이동한다. 

노란색 - 시작 / 주황색 - 도착

물론 말단 노드의 여부가 중요한 것은 아니다. 4번째 예시를 보면 노드 2는 말단 노드인데도 트리의 지름만큼 이동하지 않았다. 즉, 특정 노드를 기준으로 1번만 탐색해서는 움직인 거리가 트리의 지름이라고 확신할 수가 없다.

 

대신에 이렇게 이전 탐색에서 최종적으로 도착한 노드를 시작점으로 다시 탐색하는 과정을 추가로 거쳐야 한다. 

정리하자면 트리의 지름을 구하기 위해서는 2번의 노드 탐색이 필요하다.

1. 특정 노드에서 가장 멀리 떨어진 노드를 찾는 탐색
2. 1.에서 찾은 노드에서 가장 멀리 떨어진 노드를 찾는 탐색 

2의 시작점과 2.의 도착점 사이의 거리 = 트리의 지름

 

노드 탐색 2번이면 어떤 노드에서 시작하는지와 관계없이 항상 트리의 지름을 구할 수 있기 때문에 가장 합리적인 알고리즘이라고 볼 수 있다.

 

🤦‍♀️유의 사항

DFS가 조금 더 빠르다.

---

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

n = int(input())

#################################################
# 1967번 
tree = {i:[] for i in range(n+1)}
for _ in range(n-1):
    p, c, w = map(int, input().split())
    tree[p].append([c, w])
    tree[c].append([p, w])

#################################################
# 1167번
tree = {}
for i in range(n):
    a = list(map(int, input().split()))
    tree[a[0]] = []
    for j in range(1,len(a),2):
        if a[j]==-1 or a[j+1]==-1:
            break
        tree[a[0]].append([a[j],a[j+1]])

#################################################
# BFS
def BFS(root):
    ch = [0]*(n+1)
    ch[root] = 1
    mx_v, mx_d = 0, 0
    dQ = deque([[root,0]])
    while dQ:
        pv, pd = dQ.popleft()
        for nv, d in tree[pv]:
            nd = d+pd
            if not ch[nv]:
                ch[nv] = 1
                dQ.append([nv,nd])
                if nd > mx_d:
                    mx_d = nd
                    mx_v = nv
    return mx_v, mx_d

vertex, distance = BFS(1)
print(BFS(vertex)[1])

#################################################
# DFS
def DFS(pv, pd):
    global mx_v, mx_d    
    for nv, d in tree[pv]:
        if not ch[nv]:
            ch[pv] = 1
            nd = d+pd
            DFS(nv, nd)
            if nd > mx_d:
                mx_d = nd
                mx_v = nv

mx_v, mx_d = 0, 0
ch = [0]*(n+1)
DFS(1,0)
ch = [0]*(n+1)
DFS(mx_v, 0)
print(mx_d)