1167번. 트리의 지름

http://boj.kr/1167 

1167번: 트리의 지름

 

맨 처음에는 인접 행렬을 통해서 완전 탐색을 하려고 했지만 메모리 초과가 났다.

우선 인접 행렬을 쓰면 메모리 초과가 난다. 인접 리스트를 써야 한다.

간선에 가중치가 존재하기 때문에 adj[시작노드] = [도착노드, 노드 간 거리] 이런 식으로 인접 리스트를 구성해주었다.

 

그리고 완전 탐색을 하면 아마 시간 초과가 날 것이다. 여기서는 특정 알고리즘(?)이 필요한데,

트리에서 아무 노드나 잡아서 그 노드에서 가장 먼 노드를 구한 후, 그 노드에서 또 가장 먼 노드를 구하면 그게 트리의 지름이 된다는 것이다.

생각을 해 보면 아무 노드나 잡은 후 가장 먼 노드를 구하면 루트나 리프 노드일 것이다. 거기서부터 가장 먼 노드를 구하면 그 사이 거리가 트리에서 가장 긴 거리가 될 것이다.

그러니까...DFS를 두 번 도는 이유는 첫번째는 루트나 리프, 어쨌든 끝점을 구하기 위해서라고 해도 될 것 같다. 두번째는 거기서부터 제일 먼 점을 구하는 거고.

 

일단 트리의 지름을 구하는 알고리즘은 이렇고, 한 노드에서 가장 먼 노드를 구하는 것도 은근 일이다.

나는 최단경로찾기 할 때처럼 max_dist 를 전역변수로 두고, DFS로 계속해서 자식 노드를 찾아가되 리프 노드를 발견하면 거리를 비교해 max_dist를 갱신하는 방식으로 풀었다.

 

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


def dfs(parent, dist, visited):
    global max_dist
    visited[parent] = 1
    leaf = True
    for child in adj[parent]:  # child = [노드번호, 거리]
        if not visited[child[0]]:
            leaf = False
            dfs(child[0], dist+child[1], visited)
    if leaf:  # leaf or root
        if max_dist[1] < dist:
            max_dist = [parent, dist]


n = int(input())

adj = {i: [] for i in range(1, n+1)}  # 인접 리스트
for _ in range(n):  # 입력 받기
    tmp = list(map(int, input().split()))
    start = tmp[0]
    endpoint = 1
    while tmp[endpoint] != -1:
        adj[start].append([tmp[endpoint], tmp[endpoint+1]])  # adj[시작점] = [[도착점, 거리], ...]
        endpoint += 2

max_dist = [-1, float('-inf')]  # [노드 번호, 거리]
visited = [0 for _ in range(n+1)]
dfs(1, 0, visited)  # 아무 점에서부터 제일 먼 점을 찾는다. 여기서는 1을 선택

max_dist[1] = float('-inf')  # 위에서 구한 점으로부터 최대 거리를 구하기 위해 값 초기화
visited = [0 for _ in range(n+1)]
dfs(max_dist[0], 0, visited)  # 아까 아무 점에서 제일 먼 점을 구했으면, 그 점에서 제일 먼 점을 또 구한다

print(max_dist[1])