문제

BOJ 1967: 트리의 지름 https://www.acmicpc.net/problem/1967

풀이

조건

• 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있다.
• 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다.

풀이 순서

• 트리 구조를 양방향 그래프로 거리 정보를 포함해 만든다.
• 루트 노드(1번)부터 방문처리를 해주며 탐색을 시작한다.
• DFS를 사용해 가장 멀리 있는 노드의 번호를 구한다.
• 방금 구한 가장 멀리 있는 노드의 번호를 시작으로 다시 가장 멀리 있는 노드를 DFS를 사용해 구한다.

코드

Python

import sys
sys.setrecursionlimit(10**9)


# DFS를 사용해 시작 노드부터 가장 멀리 있는 노드를 찾는다
def dfs(node, distance):
    global max_len_node, max_len, checked
    
    # 현재 노드가 리프 노드 라면(연결된 노드가 부모 노드 밖에 없음)
    if len(graph[node]) == 1:
        # 최장 거리를 갱신하고 최장 거리에 해당하는 노드 저장
        if max_len < distance:
            max_len = distance
            max_len_node = node
    
    # 연결된 다음 노드 탐색
    for nxt in graph[node]:
        if checked[nxt[0]]:
            continue
        checked[nxt[0]] = True
        # 연결된 다음 노드 까지의 거리를 더해 파라미터로 넘겨줌
        dfs(nxt[0], distance + nxt[1])


n = int(sys.stdin.readline().rstrip())

# 트리 구조를 양방향 그래프로 거리 정보를 포함해 만듦
graph = [[] for _ in range(n + 1)]
for _ in range(n-1):
    p, c, dist = map(int, sys.stdin.readline().rstrip().split())
    graph[p].append([c, dist])
    graph[c].append([p, dist])

max_len = 0
max_len_node = 0
checked = [False for _ in range(n + 1)]

# 루트 노드(1번)부터 방문처리를 해주며 탐색 시작
checked[1] = True
dfs(1, 0)

# 루트 노드(1번)에서 가장 멀리 있는 노드 저장
a = max_len_node

max_len = 0
max_len_node = 0
checked = [False for _ in range(n + 1)]

# 가장 멀리 있는 노드(a 변수에 저장한 노드 번호)에서 가장 멀리 있는 노드 탐색 시작
checked[a] = True
dfs(a, 0)

# 가장 멀리 있는 노드(a 변수에 저장한 노드 번호)에서 가장 멀리 있는 노드 저장
b = max_len_node
b_len = max_len

# 정답 출력
print(b_len)

정리

• DFS를 2번 사용해 거리를 구하는 방식을 사용했다.