[백준(파이썬/Python)] 1167_트리의 지름

 

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

1167번: 트리의 지름

 

- 트리의 지름을 구하는 방법에 대한 약간의 사전지식(?)이 있어야 쉽게 풀 수 있는 문제입니다.

 

 

- 트리의 지름을 구하는 공식은 아래 주석에서 설명한 것처럼 크게 세 단계를 거칩니다.

1. 트리에서 임의의 정점 x를 찾는다.

2. 정점 x에서 가장 먼 정점 y를 찾는다.

3. 정점 y에서 가장 먼 정점 z를 찾는다.

--> 트리의 지름은 정점 y와 정점 z를 연결하는 경로다.

 

이에 대한 자세한 증명 과정은 아래 블로그를 참고했습니다.

https://blog.myungwoo.kr/112

트리의 지름 구하기

 

따라서 이 문제는 모든 정점에 대하여 BFS를 수행하는 방식으로는 문제의 시간복잡도 제한을 맞출 수 없기 때문에 위에서 설명한 트리의 지름을 구하는 방식으로 단 두 번의 BFS를 통해 트리의 지름을 구해야 합니다.

 

최종적인 코드는 아래와 같습니다.

 

[풀이]

from collections import defaultdict, deque
import sys


# bfs로 끝 정점까지 거리 구하기
def getDistance(start):
    randomNode, maxDistance = 0,  0
    visited = [False] * (v+1)
    visited[start] = True
    q = deque()
    q.append((start, 0))

    while q:
        currNode, distance = q.popleft()

        if maxDistance < distance:
            maxDistance = distance
            randomNode = currNode

        for childNode, dist in tree[currNode]:
            if not visited[childNode]:
                visited[childNode] = True
                q.append((childNode, distance + dist))

    return randomNode, maxDistance

v = int(input())

# 트리 정보 입력받기
tree = defaultdict(list)
for _ in range(v):
    line = list(map(int, sys.stdin.readline().split()))
    parent = line[0]
    for i in range(1, len(line)-1, 2):
        child, dist = line[i], line[i+1]
        tree[parent].append((child, dist))

# 트리의 지름 구하기
# 1. 트리에서 임의의 정점 x를 찾는다.
# 2. 정점 x에서 가장 먼 정점 y를 찾는다.
# 3. 정점 y에서 가장 먼 정점 z를 찾는다.
randomNode, maxDistance = getDistance(1)
randomNode, maxDistance = getDistance(randomNode)
print(maxDistance)