[BOJ][Python]1167 풀이

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

1167번: 트리의 지름

from collections import deque
import sys
ssr = sys.stdin.readline

n = int(ssr())
adj_list = [[] for _ in range(n+1)]
for _ in range(n):
    line = list(map(int, ssr().split()))
    for i in range(1, len(line), 2):
        if line[i] != -1:
            adj_list[line[0]].append((line[i], line[i+1]))
q = deque([(1, 0)])
visited = [False for _ in range(n+1)]
visited[1] = True
start_node = 0
ans = 0
while q:
    cur_node, cur_dist = q.popleft()
    if ans < cur_dist:
        start_node, ans = cur_node, cur_dist
    for next_node, next_dist in adj_list[cur_node]:
        if visited[next_node] == False:
            q.append((next_node, cur_dist+next_dist))
            visited[next_node] = True
q.append((start_node, 0))
visited = [False for _ in range(n+1)]
visited[start_node] = True
while q:
    cur_node, cur_dist = q.popleft()
    ans = cur_dist if ans < cur_dist else ans
    for next_node, next_dist in adj_list[cur_node]:
        if visited[next_node] == False:
            q.append((next_node, cur_dist+next_dist))
            visited[next_node] = True
print(ans)

트리의 지름을 처음 풀면 편견 때문에 넘겨짚는 오류를 범할 수 있는 문제라고 생각합니다. 저도 그랬으니까요. 트리에 루트 노드가 있다는 생각 때문에 당연히 루트 노드에서 제일 먼 노드까지의 길이가 지름이겠거니 하고 생각하기 쉬운데 그렇지 않은 경우가 있을 수도 있다는 부분을 생각하셔야 합니다.

 

그래서 문제 풀이를 진행해보면 먼저 루트 노드에서 제일 멀리 있는 노드를 하나 찾습니다(처음에 가장 멀리있는 노드를 구하는 건 굳이 루트 노드에서 시작하지 않아도 됩니다). 그리고 그 노드에서 가장 멀리 있는 노드를 구하면 각자가 양끝에 존재하는 셈이 되니까 그게 지름이 되겠죠. 그래프 탐색을 두 번 사용하면 되는 것입니다.