[BOJ] 1167. 트리의 지름

www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

문제: 주어진 트리에서 트리의 지름을 구하여라

 

문제 이해하기!!

트리의 지름이란 원본 문제를 보면 설명이 나와있는데요,

임의의 정점에서 임의의 정점까지의 거리가 최대인 것을 뜻합니다.

그럼 어떻게 구해야할까요?

정점의 갯수는 10만으로 플로이드-와샬 알고리즘은 못 씁니다.

그럼 다익스트라를 써도 될까요?

으음.. DP로 저장한다고 하더라도 여러 정점을 살펴봐야하기에 힘들죠.

좀 더 기본적인 방향으로 가보면 DFS, BFS가 있습니다.

DFS, BFS로 이걸 어떻게 풀어할 수 있는데, 푸는 방법이 있어요!

좀 색다르면서 허무한 방법입니다.

 

그래서 푼 방법은

1. 임의의 정점에서 최대로 긴 거리의 정점을 구합니다.

2. 해당 정점에서 다시 최대로 긴 거리를 구하면 트리의 지름이 나옵니다.

 

간단하죠?

근데 진짜 왜 이렇게 풀어지는지 모르겠을 수도 있어요.

하지만 트리의 성질과 그림으로 그려보면 바로 이해할 수 있을 겁니다.

한 정점에서 제일 긴 정점까지 가면 해당 정점은 우리가 처음 시작했던 부분에서 제일 긴 정점이라고 볼 수 있죠?

그 정점에서는 최대로 긴 정점을 찾을 수 있는 조건이 생겨요.

그 조건이라는 것은 해당 정점이 이 트리의 지름으로 그린 원에 닿인다는 것이에요.

 

음...

조금 어렵게 이야기한 것 같아서 다시 설명하자면

트리의 지름이란 것이 트리 안, 임의의 점에서 임의의 점까지 최대로 긴 길이잖아요.

그 경로를 쭉펴서 원의 지름으로 만들어요. 그럼 하나의 원이 생기겠죠?

이 때, 아무 정점이나 하나 선택해서 경로를 그리면 그 지름의 두 마지막 부분 중 하나에 닿는다는 말이에요.

그럼 해당 정점에서 지름의 반대 정점을 찾으면 해당 길이을 찾을 수 있습니다.

 

코드:

from collections import defaultdict
from heapq import *
from sys import stdin
input = stdin.readline


N = int(input())
tree = defaultdict(list)

def dfs(s):
    S = tree[s][:]
    res = 0
    nss = 0
    visit[s] = True
    while S:
        nc, ns = S.pop()
        if visit[ns]:
            continue
        visit[ns] = True
        for xc, xs in tree[ns]:
            S.append((xc + nc, xs))
        if res < nc:
            res = nc
            nss = ns
    if s == 1:
        return nss
    else:
        return res

for _ in range(N):
    vertex_info = list(map(int, input().split()))
    for i in range(1, len(vertex_info)-1, 2):
        tree[vertex_info[0]].append((vertex_info[i+1], vertex_info[i]))

visit = [False] * (N+1)
ns = dfs(1)
visit = [False] * (N+1)
print(dfs(ns))