(Python/🥇1)백준알고리즘 12912번 : 트리 수정

 

문제 바로가기 

트리 수정

문제:

N개의 정점으로 이루어진 트리 T가 있다. 트리의 각 정점은 0번부터 N-1번까지 번호가 매겨져 있다.

• 트리에서 임의의 두 정점을 연결하는 단순 경로의 개수는 1개이다.
• 두 정점사이의 거리는 두 정점을 연결하는 단순 경로상에 있는 간선의 가중치의 합이다.
• 트리의 지름은 트리에 존재하는 모든 경로 중에서 가장 긴 것이다.

홍준이는 T에서 간선을 하나 제거하고, 간선을 하나 추가하려고 한다. 이때, 추가하는 간선의 가중치는 제거한 간선의 가중치와 같아야 하며, 간선을 추가한 이후에도 트리를 유지해야 한다.

이때, 홍준이가 만들 수 있는 트리 중에서 지름이 가장 큰 것을 구하는 프로그램을 작성하시오.

 

입력:

첫째 줄에 트리 정점의 개수 N이 주어진다. (2 ≤ N ≤ 2,000) 둘째 줄부터 N-1개의 줄에는 트리를 이루는 간선이 주어진다. 간선은 from, to, cost와 같이 세 가지 정수로 이루어져 있으며, from과 to를 연결하는 간선의 가중치가 cost라는 뜻이다. (1 ≤ cost ≤ 1,000,000,000)

출력:

첫째 줄에 홍준이가 만들 수 있는 트리 중에서 가장 지름이 큰 것의 지름을 출력한다.

 

풀이:

 

트리는 연결되어있다.

 

근데 여기서 한 선을 자르게되면 2개의 트리가 완성되게된다.

 

그럼 그 두개의 트리의 지름을 구해주고

 

그 두 개의 트리를 연결해주면 두 개 트리의 최댓값이 될것이다.

 

그럼 모든 선분을 다 없애면서 ->2개의 트리나옴 -> 트리의 지름과 사라진 간선의 가중치를 더해줬을때 가장 큰 값을 더해주면 된다.

 

 

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


# BFS 로 제일 먼거 찾아준다.
def BFS(start):
    visited = [-1] * (n + 1)
    visited[start] = 0
    queue = deque([(start, 0)])  # 노드와 해당 노드까지의 가중치 값을 큐에 저장
    max_distance = (start, 0)  # 가장 먼 노드와 해당 노드까지의 가중치 값을 저장하는 변수

    while queue:
        node, distance = queue.popleft()
        visited[node] = distance

        for next_node, next_cost in graph[node]:
            if visited[next_node] == -1:
                new_distance = distance + next_cost
                queue.append((next_node, new_distance))

                if new_distance > max_distance[1]:  # 현재까지 가장 먼 노드보다 더 먼 노드를 발견하면 갱신
                    max_distance = (next_node, new_distance)

    return max_distance


def find_node(start):
    farthest_node, a = BFS(start)
    b, result = BFS(farthest_node)

    return result


n = int(input())
graph = [[] for _ in range(n)]
path = []
for _ in range(n - 1):
    u, v, e = map(int, sys.stdin.readline().rstrip().split())
    graph[u].append((v, e))
    graph[v].append((u, e))
    path.append((u, v, e))

rst = -1e9
for u, v, e in path:
    graph[u].remove((v, e))
    graph[v].remove((u, e))

    a = find_node(u)
    b = find_node(v)

    rst = max(rst, a + b + e)

    graph[u].append((v, e))
    graph[v].append((u, e))
print(rst)