[BOJ][Python]1967 풀이

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

1967번: 트리의 지름

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

n = int(ssr())
adj_list = [[] for _ in range(n+1)]
for _ in range(n-1):
    line = list(map(int, ssr().split()))
    adj_list[line[0]].append((line[1], line[2]))
    adj_list[line[1]].append((line[0], line[2]))
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)

1167번과 완전 똑같은 문제라길래 공짜 점수다 싶어서 풀어봤습니다. 약간은 다른 점이 있는데 입력으로 모든 노드에 대한 정보가 주어지지 않는다는 것입니다(예제를 기준으로 5번 노드와 9번 노드간에 간선이 있는 것이 주어지는데 1167번이라면 9번과 5번에 다시 간선이 있다는 것이 입력으로 나오지만 1967은 그렇지 않습니다). 이 쪽이 훨씬 입력으로는 바람직하다고 생각이 드네요. 똑같은 간선을 굳이 두 번이나 입력으로 줄 필요는 없겠죠.

 

트리의 지름 문제에서 조심해야할 부분은 루트 노드의 존재로 자연스럽게 루트 노드가 지름의 한 쪽 끝이 될 것이라는 무의식적인 생각이 들 수 있다는 것입니다. 루트 노드가 지름의 한 쪽 끝이 될 수도 있겠지만 아닐 수도 있다는 부분을 생각해보시면 좋을 것 같아요(다행히 1967번에는 그림으로 그 경우를 잘 줘서 착각을 미연에 방지할 수 있습니다). 그래서 그래프 탐색 알고리즘을 두 번 사용해서 처음 한 번으로 지름의 한 쪽 끝을 찾고, 그 다음으로 나머지 한 쪽 끝을 찾은 다음 거리를 구하면 되겠습니다.