[백준 1167 파이썬] 트리의 지름 (골드 3, 트리)

알고리즘 유형 : 트리, BFS, DFS
풀이 참고 없이 스스로 풀었나요? : X

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

SOLVE 1

BFS 풀이

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

V = int(input())
tree = [[] for _ in range(V+1)]
# 2차원 리스트에 트리 저장(연결 그래프)
for _ in range(V):
    line = list(map(int, input().split()))
    cnt_node = line[0]
    idx = 1
    while line[idx] != -1:
        adj_node, adj_cost = line[idx], line[idx+1]
        tree[cnt_node].append((adj_node, adj_cost))
        idx += 2

def BFS(start):
    q = deque()
    q.append((start, 0))
    visited = [-1]*(V+1)
    visited[start] = 0
    res = [0, 0] # start로부터 가장 먼 거리에 있는 노드와 거리 값
    
    while q:
        cnt_node, cnt_dist = q.popleft()
        
        for adj_node, adj_dist in tree[cnt_node]:
            if visited[adj_node] == -1:
                cal_dist = cnt_dist + adj_dist
                q.append((adj_node, cal_dist))
                visited[adj_node] = cal_dist
                if res[1] < cal_dist:
                    res[0] = adj_node
                    res[1] = cal_dist
        
    return res
    
# 트리 지름 공식 참고
# u-v가 지름이라고 하자. 임의의 점 x에서 가장 먼 거리의 노드 y는
# 반드시 u 또는 v이다. 따라서 y에서 BFS를
# 한번 더 해주면 지름을 구할 수 있다.
point, _ = BFS(1)
print(BFS(point)[1])

SOLVE 2

DFS 풀이

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

V = int(input())
tree = [[] for _ in range(V+1)]
# 2차원 리스트에 트리 저장(연결 그래프)
for _ in range(V):
    line = list(map(int, input().split()))
    cnt_node = line[0]
    idx = 1
    while line[idx] != -1:
        adj_node, adj_cost = line[idx], line[idx+1]
        tree[cnt_node].append((adj_node, adj_cost))
        idx += 2

visited = [-1]*(V+1)
visited[1] = 0

# 리턴 값 없음. visited에 모든 노드까지의 거리 저장
def DFS(node, dist):
    for v, d in tree[node]:
        cal_dist = dist + d
        if visited[v] == -1:
            visited[v] = cal_dist
            DFS(v, cal_dist)
    return
            
DFS(1, 0)
tmp = [0, 0]
# 최대 거리에 있는 노드 찾기
for i in range(1, len(visited)):
    if visited[i] > tmp[1]:
        tmp[1] = visited[i]
        tmp[0] = i

# 찾은 노드와, 찾은 노드에서 DFS 돌려 찾은 최대 거리 노드가 지름의 양 끝점
# 이 논리의 증명은 따로 알아보자
# 논리 : 임의의 노드에서 최대 거리에 있는 노드는 반드시 트리의 지름의 양 끝점 중 하나이다.
visited = [-1]*(V+1)
visited[tmp[0]] = 0
DFS(tmp[0], 0)

print(max(visited))

풀이 요약

1. 이 문제를 봤을 때 플로이드 워셜이나 모든 노드에서 BFS나 DFS를 돌리고 그 중에서 최대 거리를 출력하는 로직을 생각해낼 수 있다.

   그러나 V가 $10^6$까지라서 TLE가 난다.

   그래서 이 문제는 트리의 지름과 관해 증명된 성질을 이용하면 된다.

   트리에서 임의의 노드에서 최대 거리에 있는 노드는 반드시 트리의 지름의 양 끝점 중 하나이다.

   이 논리의 증명은 ji.o.n.e
   블로거분께서 아주 잘 정리해주셨으니 참고하자.

2. 위 로직대로, 아무 노드에서나 BFS 또는 DFS를 한 번 돌리고 그 노드에서의 최대 거리에 있는 노드를 찾아낸다.

   그 후, 찾아낸 노드에서 한번 더 BFS, DFS를 돌리면 그 때의 최대 거리가 곧 트리의 지름 길이이다.

3. 참고로, 탐색할 때 탐색 과정에서 최대 거리와 그 때의 노드를 계속 갱신해줘도 되고,

   visited를 업뎃해주면서 탐색이 끝난 후 순회하면서 최대 값을 찾아서 최대 거리를 찾아내도 된다.

배운 점, 어려웠던 점

• 트리의 지름에 관한 성질을 하나 알게 되었고, 내가 DFS에 조금 미숙하다는 점을 깨달을 수 있는 문제였다.