[BAEKJOON]1167 트리의 지름 - Python

문제 요약

• 알고리즘 분류:DFS, 트리
• 난이도: Gold2
• 문제내용:
  • 길이가 가장 긴 트리의 지름을 구해라
  • 노드개수 V, 그 다음 줄은 맨 앞에 노드 번호, 그 뒤는 -1 까지 노드와 연결된 노드 길이 여러개 준다.

• 사이트: https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

문제풀이

   이번에는 문제 유형은 트리와 DFS 탐색 유형인 문제이다. 트리와 DFS관한 자세한 설명은 아래의 사이트에서 확인 해보면된다.

• 트리: https://jih3508.tistory.com/87

[알고리즘 이론] 트리(Tree)

• DFS: https://jih3508.tistory.com/94

[알고리즘 이론] 깊이 우선 탐색(DFS)

문제 접근 방법

모든 노드를 출발점에서 길이를 구하면 O(V(V + E)) e가 최대개수가 V ^ 2 일수가 있어서 O(V ^ 3)이라는 시간 복잡도가 나올수있다.  그러면 노드 최대개수가 1,000개이면 시간 초과가 나올것이다.  이런 문제는 푸는 방법은 어떤 노드간에 거리가 긴  노드 한개를 탐색 한번만에 찾아 내면 O(V^2)시간 복잡도가 나올것이다.

 어떤 노드간에 거리가 긴  노드 한개를 탐색하는 방법은 아무 x노드에서 dfs탐색해서 거리가 가장 긴 노드를 탐색한 다음 그 노드로 부터 다시 dfs 탐색해서 거리가 긴것을 구하면 된다. 왜 그런지는 여기 사이트에서 참조하면될거 같다.

https://blog.myungwoo.kr/112

트리의 지름 구하기

 위에는 왜그런지 증명하는 것이고 문제 예제로 간단하게 설명하겠다.

 예제 1번을 트리로 나타 내는 것이다. 그러면 리프 노드는 1, 5, 2중 하나만 선택 하면된다.

 위 표는 각 노드 간의 거리를 나타낸 것이고 각 노드마다 거리 긴것은 노란색으로 표시했다. 위 표를 보면 5를 제외 하면 가장 멀리 있는 노드는 5이다. 그러면 우리가 알수있는 것은 어떤 x노드에서 y까지 가장 멀리 있는 노드는 한 개빼고는 같기 때문에 아무 노드에서 시작해서 가장 멀리있는 노드를 찾아낸 다음 그 노드에서 가장 멀리있는 노드와의 거리를 출력하면된다.

정리

1. 아무 노드 x를 지정해서 dfs탐색해서 가장 멀리 있는 노드를 가져온다.
2. 가장 멀리있는 노드를 시작해서 dfs탐색한 다음 가장 긴 거리를 출력한다.

 

Code

V = int(input())

def dfs(start):
    stack = [start]
    distance = [0] * (V + 1)
    while stack:
        node = stack.pop()
        for next_node, weight in tree[node]:
            if distance[next_node] == 0 and next_node != start:
                distance[next_node] = distance[node] + weight
                stack.append(next_node)
    return distance.index(max(distance)) ,max(distance)

tree = {i : [] for i in range(1, V + 1)}
for _ in range(V):
    node, *array = map(int, input().split())
    for i in range(len(array)//2):
        tree[node].append((array[i * 2], array[i * 2 +1]))

node = dfs(3)[0]

print(dfs(node)[1])