[BOJ/백준] 19581 두번째 트리의 지름

import sys

input = sys.stdin.readline
def dfs(node,flag,*args):
    stack = [(node,0)]
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    if not flag:
        visited[args[0]] = True
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance

        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,distance+graph[node][next_node]))
    
    temp = []

    for i in range(1,N+1):
        temp.append((distance_list[i],i))
    temp.sort(key=lambda x :-x[0])
    if flag:
        return_value = temp[0][1]
    else:
        return_value = temp[0][0]
    return return_value


N = int(input())
graph = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay

first_point = dfs(1,True)
second_point = dfs(first_point,True)

first_value = dfs(first_point,False,second_point)
second_value = dfs(second_point,False,first_point)

print(max(first_value,second_value))

 이 문제는 트리의 지름을 구하는 방법을 응요한 문제이다.

 

총 4번의 dfs를 통해 두번째 트리의 지름을 알 수 있다.

 

첫번째 dfs를 통해 아무지점에서 가장 먼 지점을 구한다.

 

이 지점은 지름을 구성하는 한 점이 될것이다.

 

 

두번째 dfs를 통해 첫번째 dfs에서 구한 점에서 가장 먼 점을 구한다.

 

그러면 이 점은 트리의 지름을 구성하는 가장 먼 점이 될것이다.

 

 

이렇게 2번의 dfs를 통해 우리는 가장 먼 점 2개를 구했다.

 

그러면 이 2점을 각각 dfs를 돌려, 가장 먼 점에서 2번째인 것을 찾아낸다.

 

그리고 이렇게 두 거리를 구한 뒤 그 중에 더 큰 점을 선택하면 되는 문제이다.

 

 

import sys

input = sys.stdin.readline
def dfs(node):
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    stack = [(node,0)]
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,graph[node][next_node]+distance))
    return distance_list

N = int(input())
graph = [{} for _ in range(N+1)]

for _ in range(N-1):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay


distance1 = dfs(1)
far_point1 = distance1.index(max(distance1))
distance2 = dfs(far_point1)
far_point2 = distance2.index(max(distance2))
distance3 = dfs(far_point2)
result = sorted(distance2+distance3)[-3]
print(result)

단 3번의 dfs를 통해 구하는 방법도 있다.

 

이 방법은 지름을 구성하는 2점의 전체길이를 한 리스트로 정하고 뒤에서 3번째를 출력해주는 것이다.

 

왜냐하면 한 리스트당 한 지점에서 가장 먼 지점은 서로 자신들이기 때문에, 그 2점을 제외하고 그 다음번으로 큰 것이

 

두번째 트리의 지름의 답이된다.