[백준] #1167 트리의 지름(python)

📌문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제 입력

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

예제 출력

11

백준 1167번 문제

💡Idea

트리의 지름을 어떻게 구해야하느냐를 알면 쉬워지는 문제입니다.

처음에는 트리의 지름이 leaf node(트리에서 가장 끝의 노드)로부터 시작하여 탐색할 수 있는 노드 끝까지의 길이 중 가장 긴 값을 구하면 된다고 생각을 했습니다.

하지만 이 방법은 계산이 겹치는 경우가 많아 시간 초과가 발생합니다.

트리🎄의 지름은 아래와 같이 구할 수 있습니다.

1. 임의의 노드 n을 선택하여 n으로부터 가장 먼 노드 v를 구한다.
2. 구한 노드 v로부터 가장 먼 노드 u를 구한다.
3. v와 u 사이의 거리가 바로 트리의 지름이다.

시간복잡도 : $O(N)$

💻코드

• ⏰ 시간 : 824 ms / 메모리 : 107996 KB

import sys
input = sys.stdin.readline

V = int(input())
tree = {}

for _ in range(V): # 트리 dictionary로 생성
    temp = list(map(int, input().split()))
    tree[temp[0]] = []
    for i in range(1, len(temp) - 2, 2):
        tree[temp[0]].append((temp[i], temp[i + 1]))

ans = set()
visited = set()


def dfs(v, l): # 재귀 dfs
    visited.add(v)
    for n, d in tree[v]:
        if n not in visited: dfs(n, d + l)
        else: ans.add((v, l))


dfs(1, 0) # 1. 임의 노드에서 dfs
visited = set()
dfs(max(ans, key=lambda x: x[1])[0], 0) # 2. 임의 노드와 가장 먼 노드에서 dfs
print(max(ans, key=lambda x: x[1])[1]) # 3. 가장 긴 길이가 트리의 지름

🔗Reference

[백준]1167: 트리의 지름 - JAVA