[백준 - Python] 1967 - 트리의 지름

0.  문제 링크

 

 

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

1967번: 트리의 지름

---

1.  풀이 방법

 

 

문제를 보고 이건 탐색 기법을 써야겠다고 생각을 했다.

문제 무작정 DFS, BFS를 쓰는 건 좀 아닌 것 같았다. 왜냐면 모든 노드에서 다른 노드를 탐색하는 방법을 사용하면 n^2이 될 것 같았기 때문이다.

어떻게 최장거리를 탐색할 것인가에 대해 고민을 했다.

방금 글 쓰면서 떠오른건데 TSP를 조금 손 봐서 최장거리를 찾아낼 수 있을 것 같다는 생각이 들었다.

 

아무튼 내가 푼 방법은 다음과 같다.

1. 모든 리프 노드를 찾는다.
2. 어차피 최장 거리는 보통 리프 to 리프, 혹은 리프 to 헤드 노드 둘 중에 하나에 있기 때문이다.
3. A 리프 노드에서 모든 부모(부모의 부모 등)와 해당 부모까지의 거리를 찾는다.
4. B 리프 노드에서 부모를 찾아가면서 A 리프 노드와 겹치는 부모를 찾는다.
5. 겹치는 부모를 찾았다면 A와의 거리와 B와의 거리를 찾으면 된다.

해당 방법은 python3로는 시간 초과가 나고, pypy로 풀었다.

더 좋은 방법은 분명 있을텐데, 뭔가 해당 방식에 꽃혀서 저렇게 풀었다.

 

그림으로 그려보자면 다음과 같다.

 

그림이 허접해서 죄송합니다..

아무튼 이런 방식으로 풀었다....

---

2.  코드

 

 

import sys
input = sys.stdin.readline

n = int(input())
my_par = dict()
leaf_node = set()
par_node = set()
maximum = 0

for _ in range(n - 1):
    par, ch, weight = map(int, input().split())
    my_par[ch] = [par, weight]
    par_node.add(par)       # 최하단 노드를 찾기 위해, 부모가 된 노드도 저장함
    leaf_node.add(ch)       # 최하단 노드를 찾기 위함

leaf_node = list(leaf_node - par_node)      # 부모가 된 노드를 모두 삭제함

weight_dict = dict()
for idx, node in enumerate(leaf_node):      # 맨 아래 노드부터 시작함
    weight_dict[node] = 0
    while True:
        # 해당 반복문은 부모로 이동하면서, 맨 아래 노드부터 어떤 부모까지의 거리를 저장함
        par = my_par[node][0]
        weight_dict[par] = my_par[node][1] + weight_dict[node]
        node = par
        if node not in my_par:
            break

    for other_node in leaf_node[idx + 1:]:
        score = 0
        while True:
            # 해당 반복문은 다른 맨 아래 노드부터 어떤 부모까지의 거리를 저장함
            par = my_par[other_node][0]
            score += my_par[other_node][1]
            other_node = par
            if other_node in weight_dict:
                # 만약 while문에서 찾은 부모와 일치하다면 그대로 끝냄
                break

        maximum = max(maximum, score + weight_dict[other_node])
    maximum = max(maximum, weight_dict[1])      # 1까지만 가는게 더 빠를 수도 있음

    weight_dict.clear()

print(maximum)

---

3.  마무리