[Python 3] BOJ - 1167 "트리의 지름"

 # 문제 링크 : https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 # 풀이 : 

개인적으로 문제의 핵심은 트리의 지름과 관련된 내용을 아느냐 여부이다. 물론 모른다고 해도 풀 수 있지만, 모른다면 트리의 지름에 대해 검색하면 좋을 것 같다. 트리의 지름은 트리의 임의의 한 점 x를 선택하고, x에서 가장 먼 정점 y를 찾은 후, 다시 y에서 가장 먼 정점 z를 찾는다. 여기서 y와 z의 거리가 트리의 지름이다. 자세한 증명은 하단의 링크를 참고하면 된다. 아래의 링크에서는 u,v가 유일한 지름일 때 귀류법을 이용하여 어떠한 경우든 모순을 일으킨다는 큰 흐름이므로 참고하자.

증명 : https://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work

How does following algorithm for finding longest path in tree work?

또한, 트리를 이루는 두 정점은 단말 노드라는 것이다. 왜냐하면 u와 v가 트리의 지름의 두 정점일 때, 만일 v가 자식이 있다고 가정한다면, 당연히 u와 v의 자식의 거리가 더 멀기에 원래의 조건에 위배되기 때문이다.

 

 # 코드

import sys, collections

# bfs : 임의의 한점에서 가장 먼 점과 그 거리를 리턴하는 함수
# dfs로도 충분히 가능하다
def bfs(num):
    dist, node = 0,0
    q = collections.deque()
    q.append((num, 0))
    check[num] = True
    while q:
        now, now_dist = q.popleft()
        for i in adj[now]:
            # 중복방문을 막기위해 check 배열 방문 여부 확인
            if check[i[0]] == False:
                check[i[0]] = True
                # 단순히 두 정점간의 거리만 큐에 넣는 것이 아니라
                # 현재까지의 거리와 현재 정점의 거리를 더해줘야 
                # 두 정점의 총 거리이므로 now_dist와 i[1]을 더해주고 큐에 넣는다
                q.append((i[0], i[1] + now_dist))
                
                # dist 최대값 갱신과 함께 그때 어떤 노드인지도 갱신
                if now_dist + i[1] > dist:
                    dist = now_dist + i[1]
                    node = i[0]
    return dist, node

# init : 총 bfs를 두번해야 하기에 check 배열을 초기화하는 함수
def init():
    for i in range(n):
        check[i] = False

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

# 인접 리스트 생성
adj = [[] for _ in range(n)]
for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(temp) - 1, 2):
        adj[temp[0] - 1].append((temp[j] - 1, temp[j + 1]))

check = [False] * n
# 정점 0에서 시작하여 가장 먼 거리 a가 걸리는 정점 b를 찾는다
a,b = bfs(0)

# check 초기화
init()

# 현재 정점 b에서 다시 가장 먼 정점 c를 찾고 그 때의 거리를 출력
print(bfs(b)[0])