⭐⭐⭐⭐[코드트리] 트리의 지름

https://www.codetree.ai/missions/9/problems/diameter-of-tree/introduction?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

관련 백준 문제: 1867번 트리 지름

1967번: 트리의 지름

 

똑같은 코드트리 문제: 트리 간선의 길이

 

 

트리에서는 어떠한 두 정점을 고르더라도 두 정점 사이를 연결하는 경로는 유일하게 결정된다는 특징이 있습니다. 각 간선에 가중치가 있는 트리 정보가 주어졌을 때, 모든 정점 쌍에 대한 거리 중 가장 긴 경로의 길이를 트리의 지름이라고 부릅니다.

아래 그림에서 트리의 지름은 6+6+2+4=18이 됩니다.

 

 

트리의 지름을 가장 쉽게 구하는 방법은 다음과 같습니다.

1. 아무 정점이나 잡고 시작해서 DFS를 이용해 시작점으로부터 가장 먼 정점을 구합니다. 거리가 동일한 정점이 여러 개라면 아무 정점이나 골라도 괜찮습니다. 이렇게 골라진 가장 먼 정점을 x라 하겠습니다.
2. DFS를 이용해 동일한 방식으로 x를 시작점으로 하였을 때 가장 먼 정점을 구합니다. 이때 구해진 거리가 지름이 됩니다.

예로 아래 그림에서의 지름을 구해보겠습니다.

 

1번 정점을 시작으로 가장 먼 정점을 구합니다. 가장 먼 정점은 7번 정점이 됩니다.

 

 

이제 7번 정점을 시작으로 가장 먼 정점을 구합니다. 가장 먼 정점은 5가 되며, 따라서 7번 정점과 5번 정점으로 이루어져 있는 경로의 길이가 트리의 지름이 됩니다.

 

 

따라서 트리의 지름을 구하는 데 걸리는 시간은 O(N)이 됩니다.

 

 

문제 

트리의 지름이란, 임의의 두 정점 사이의 거리 중 가장 긴 거리를 뜻합니다.

1번부터 n번까지 n 개의 정점으로 이루어진 트리가 주어질 때, 트리의 지름을 구하는 프로그램을 작성하세요.

 

입력 형식

첫 번째 줄에 트리의 정점의 개수를 나타내는 정수 n이 주어집니다.

그다음 줄부터 n-1 개의 줄에 걸쳐, 트리의 각 간선이 연결하는 두 정점의 번호와 그 간선의 길이가 공백으로 구분되어 주어집니다.

• 2 ≤ n ≤ 100,000
• 주어지는 간선의 거리는 1 이상 10,000 이하입니다.

 

출력 형식

첫 번째 줄에 트리의 지름을 출력합니다.

 

 

입출력 예제

예제1

입력:

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

 

출력:

11

 

---

import sys
sys.setrecursionlimit(100000)

sys.stdin=open('input.txt', 'r')

# DFS를 통해 연결된 모든 정점을 순회합니다.
# 동시에 시작점으로부터의 거리를 같이 계산해줍니다.
def dfs(x, total_dist):
    # 노드 x에 연결된 간선을 살펴봅니다.
    for y, weight in graph[x]:
        # 아직 방문해본적이 없는 노드인 경우에만 진행합니다.
        if not visited[y]:
            visited[y] = True
            dist[y] = total_dist + weight
            dfs(y, total_dist + weight)
            
# 정점 x로부터 가장 멀리 있는 정점 정보를 찾아줍니다.
def find_largest_vertex(x):
    # visited, dist 값을 초기화해줍니다.
    for i in range(1, n + 1):
        visited[i] = False
        dist[i] = 0
    
    # 정점 x를 시작으로 하는 DFS를 진행합니다.
    visited[x] = True
    dist[x] = 0
    dfs(x, 0)
    
    # 정점 x로부터 가장 멀리 떨어진 정점 정보를 찾습니다.
    farthest_dist = -1
    farthest_vertex = -1
    for i in range(1, n + 1):
        if dist[i] > farthest_dist:
            farthest_dist = dist[i]
            farthest_vertex = i

    # 가장 멀리 떨어진 정점 번호와 그때의 거리를 반환합니다.
    return farthest_vertex, farthest_dist

if __name__=="__main__":
    # 변수 선언 및 입력:
    n = int(input())
    graph =[[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    dist = [0] * (n + 1)

    # n - 1개의 간선 정보를 입력받습니다.
    for _ in range(n - 1):
        x, y, d = tuple(map(int, input().split()))
        # 간선 정보를 인접리스트에 넣어줍니다.
        graph[x].append((y, d))
        graph[y].append((x, d))


    # 1번 노드로부터 가장 멀리 있는 노드 정보를 찾습니다.
    f_vertex, _ = find_largest_vertex(1)	# 임의의 노도로 1번 노드를 고름 2,3,4 뭐를 해도 같은 결과 나옴
    # 1번 노드로부터 가장 멀리 있는 노드의 가장 멀리 있는 노드의 거리를 구한다.
    _, diameter = find_largest_vertex(f_vertex)

    print(diameter)

 

이해하는데 좀 걸렸다. 

왜 find_largest_vertext 함수를 두번 불러야하는지 이해가 가지 않았는데 

문제에서는 처음부터 딱 1번부터 n번까지 노드가 주어지는데 

1번 노드가 가장 꼭대기 루트 노드가 아닐 수 있다. 

따라서 임의의 노드를 골라 가장 멀리 있는 노드를 찾고 거기서 또 가장 멀리 있는 노드를 찾아야 트리의 지름이 된다. 

즉 find_largest_vertext(1)이 아니라 find_largest_vertext(4)로 시작하여도 결과는 똑같이 나온다. 

 

---

+ 다른 방법 

트리 간선의 길이 구하는 문제랑 같음 

간선에 가중치가 부여된 트리에서, 두 점 사이의 거리 중 가장 긴 값을 구하는 프로그램을 작성하세요.

트리에서 두 점 사이의 거리란, 두 점을 잇는 단순 경로에 포함된 모든 간선의 가중치의 총합을 의미합니다.

import sys
sys.setrecursionlimit(100000)


# 모든 노드의 정점을 탐색하는 DFS를 진행합니다.
def DFS(x):
    global max_dist, last_node
    
    for y, w in graph[x]:   
        if not visited[y]:      # 이미 방문한 정점이면 스킵합니다.
            visited[y] = True
            dist[y] = dist[x] + w

            # 현재 정점을 기준으로 가장 먼 노드를 찾습니다.
            if dist[y] > max_dist:
                max_dist = dist[y]
                last_node = y

            DFS(y)
        

if __name__=="__main__":
    # 변수 선언 및 입력:
    n = int(input())
    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    dist = [0] * (n + 1)
    max_dist = 0
    last_node = 0

    # n - 1개의 간선 정보를 입력받습니다.
    for _ in range(n - 1):
        x, y, w = tuple(map(int, input().split()))
        graph[x].append((y, w))
        graph[y].append((x, w))


    # DFS를 통해 가장 먼 노드를 찾습니다.
    visited[1] = True
    DFS(1)

    # 가장 먼 노드에서 시작해 다시 한번 DFS를 돌려 트리의 가장 긴 거리를 찾습니다.
    for i in range(1, n + 1):
        visited[i] = False
        dist[i] = 0

    visited[last_node] = True
    DFS(last_node)

    # 트리의 가장 긴 거리를 출력합니다.
    print(max_dist)