백준(BOJ) 1167 트리의 지름(Python)

문제 내용

 

DFS를 두 번 사용하면 되는 문제.

트리의 지름을 구하는 방법은 간단하다.

임의의 한 노드에서 DFS 혹은 BFS를 실행해 가장 거리가 먼 노드를 택하고, 그 노드에서 다시 한 번 DFS를 실행하면 가장 거리가 먼 노드의 거리가 트리의 지름이 된다.

​

코드는 다음과 같다.

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
input=sys.stdin.readline
sys.setrecursionlimit(100000000)

def dfs(x,p):
    visited[x]=1
    for i in D[x]:
        a,b=i
        if not visited[a]:
            length[a]=p+b
            dfs(a,p+b)
v=int(input())
D={i:[] for i in range(v+1)}
for i in range(v):
    L=list(map(int,input().split()))
    p=L[0]
    for j in range(1,len(L)-2,2):
        D[p].append((L[j],L[j+1]))
visited=[0]*(v+1)
length=[0]*(v+1)
dfs(1,0)
p=0
l=0
for i in range(1,v+1):
    if length[i]>p:
        l=i
        p=length[i]
visited=[0]*(v+1)
length=[0]*(v+1)
dfs(l,0)
p=0
l=0
for i in range(1,v+1):
    if length[i]>p:
        l=i
        p=length[i]
print(p)

자료구조 수업 때 분명히 이 개념을 배웠을텐데, 수업을 잘 안 들어서 개념을 떠올리지 못해 검색을 통해 증명까지 새로 공부했다.

개인적으로 그리디나 DP를 별로 안 좋아하는데, 문제를 풀면서 느끼는 점은 트리 역시 그와 비슷한 정도로 싫어하는 것 같다는 점이다.

취약점이 하나 늘었으니 더 열심히 공부할 수 있을 것 같다.