[BOJ] 1967번: 트리의 지름 (DFS)

 

트리 지름 구하는 알고리즘은 정해져 있음 :: 그냥 외우기 !!!!!

(( 한 번 더 하기 ))

 

코드 링크

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

 

[ 비슷한 문제 ]

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

 

 

TIL

• 트리의 지름을 구하는 방법 중 가장 널리 사용되는 방법은 DFS(깊이 우선 탐색)를 두 번 수행하는 방식
• 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다
  • 트리에서 임의의 정점 x를 잡는다.
  • 정점 x에서 가장 먼 정점 y를 찾는다.
  • 정점 y에서 가장 먼 정점 z를 찾는다.
  • 트리의 지름은 정점 y와 정점 z를 연결하는 경로다.
• 즉, 정리하면
  • 임의의 노드(보통 루트 노드인 1번)에서 가장 먼 노드를 찾는다.
  • 이 노드를 시작점으로 다시 DFS를 수행하여 가장 먼 노드까지의 거리를 찾는다.
  • 이 두 번째 DFS에서 얻은 거리 값이 트리의 지름이다.
• 이 방식은 왜 항상 올바른 결과를 보장하는가?
  • 트리의 지름의 양 끝점 중 하나는 항상 임의의 노드에서 가장 먼 노드 중 하나이다.
  • 따라서 첫 번째 DFS로 한쪽 끝점을 찾고, 두 번째 DFS로 지름을 구할 수 있다.

 

 

Code

# GPT
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 1. 입력 받기
n = int(input().strip())
tree = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    parent, child, weight = map(int, input().split())
    tree[parent].append((child, weight))
    tree[child].append((parent, weight))  # 무방향 그래프

# 2. DFS를 통한 가장 먼 노드 찾기
def dfs(node, dist):
    global farthest_node, max_distance
    visited[node] = True
    
    if dist > max_distance:
        max_distance = dist
        farthest_node = node
    
    for neighbor, weight in tree[node]:
        if not visited[neighbor]:
            dfs(neighbor, dist + weight)

# 3. 루트(1번 노드)에서 가장 먼 노드 찾기
visited = [False] * (n + 1)
farthest_node = 0
max_distance = 0
dfs(1, 0)

# 4. 가장 먼 노드에서 다시 DFS 수행하여 지름 구하기
visited = [False] * (n + 1)
max_distance = 0
dfs(farthest_node, 0)

# 5. 출력
print(max_distance)