[BOJ/백준] 12912 트리 수정

import sys
sys.setrecursionlimit(3000)
def input():
    return sys.stdin.readline().rstrip()

def get_diameter():
    result = 0
    visited = [0 for _ in range(N)]
    def dfs(node,tag):
        nonlocal visited
        stack = [(node,0)]
        visited[node] += 1
        max_node = -1
        max_dis = 0
        while stack:
            node,dis = stack.pop()
            if dis>max_dis:
                max_dis = dis
                max_node = node
            for next_node in graph[node]:
                if visited[next_node] == tag:
                    visited[next_node] += 1
                    stack.append((next_node,dis + graph[node][next_node]))
        return [max_node,max_dis]
    for idx in range(N):
        if visited[idx] == 0:
            far_node,_ = dfs(idx,0)
            _,dis = dfs(far_node,1)
            result += dis

    return result
N = int(input())

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

result = get_diameter()
cnt = 0
for x,y,pay in origin_path:
    del graph[x][y]
    del graph[y][x]

    result = max(result,get_diameter()+pay)
    graph[x][y] = pay
    graph[y][x] = pay
print(result)

이 문제를 푼 사람도 적어서 안 알려진 문제이지만, 좋은 문제라 생각되어 다른 것보다 우선순위를 두어 복기를 했다.

 

이 문제의 조건을 읽어보면 하나의 트리가 주어지고, 이 트리의 간선 중 하나를 제거 한뒤,

 

이 간선을 트리의 구조를 지키면서, 간선을 추가해야하는 문제이다.

 

처음에 생각한 방법은, 트리의 간선을 제거하고, 임의의 두 노드를 뽑아서, 연결이 되어있지않다면 연결을 해주고,

 

cycle이나, 모든 노드를 통과하지 못하는 경우를 체크해주고, 트리의 지름을 구하는 식으로 생각을 했다.

 

하지만 이 방법은 2000C2 * 1999 * 트리의 지름을 구하는 복잡도가 되어 시간 초과가 날거라 생각을 했다.

 

이 문제를 푼 아이디어는 다음과 같다.

 

우리는 처음에 하나의 트리가 주어진다.

 

이 트리의 간선을 하나를 제거한다는 것은

 

2개의 트리가 된다는 것이다.

 

즉

이 와 같은 트리가 주어진다고 하면, 

 

 

하나의 간선을 없앤다는 것은 두개의 트리로 나뉘어진다는 것으로 볼수 있다.

 

우리는 이렇게 2개로 나뉘어진 트리를 이어주고, 트리의 지름을 최대로 구할려고 하는 것이다.

 

즉, 어느 노드 끼리 이어지는 것은 중요하지 않고, 2개의 트리를 연결했을때, 트리의 지름이 최대가 될려고 하는 것이다.

 

그러면 우리가 구하는 방법은 명확해진다 우리는 잘랐던 간선의 가중치를 그대로 연결한다.

 

그렇다하면, 2개의 트리의 어느 부분을 이었을때 가장 큰 트리의 지름이 될것인지 생각해보면,

 

명확하다. 2개의 트리에서 각각 지름을 구성하는 노드들의 끝점들을 이어주면 지름의 최대값이 될것이다.

 

즉 우리는 간선을 삭제하고, 나온 트리의 지름들을 각각 구한뒤, 자른 간선의 가중치를 더해주면

 

해당 간선을 삭제하고 연결했을때의 최대 트리의 지름을 구할 수 있게 된다.

 

 

그러면 이 방식은 간선의 개수 만큼 4번의 dfs를 하면 정답을 구할수 있게 된다.

 

여기서 나는, 2개로 나뉜 트리를 구분하기 위해, visited의 방문 회수를 기점으로, 언제 방문했는지를 구분해주었다.

 

 

이 문제는 처음에 푼 사람의 수가 워낙적고, 골1이라고 책정된 난이도 때문에 풀기 어려워보였지만,

 

문제에서 계속 강조하는 트리의 지름과 트리라는 구조라는 점에 착안해서 풀수 있었던 좋은 문제였다.