[백준 1967] 트리의 지름 [Python]

백준 1967 - 문제

백준 1967 - 입/출력

---

풀이

주어진 트리에 대해 트리의 지름을 구하면 되는 문제다.

트리의 지름이란, 트리에서 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 값을 의미한다.

즉, 문제에 나온 이미지처럼 임의의 두 정점을 길게 당길 때 가장 큰 원을 만들 수 있는 간선의 합이 트리의 지름을 의미한다.

 

그렇다면 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 정점은 어떻게 찾을까?

임의의 두 정점(x, y)과 간선의 가중치의 합이 최대가 되는 정점(v1, v2)의 관계에 있어 다음과 같다.

(x, y) 두 정점 모두 (v1, v2)와 일치할 때 : 한 번의 탐색으로 정답을 구할 수 있다.

(x, y) 중 하나의 정점(x)만 (v1, v2)의 (v1)과 일치할 때 : 한 번의 탐색으로 (v1)를 구할 수 있다.
정점(v1, y)을 가지고 재탐색을 하면 같은 논리로 (v2)를 구할 수 있다.

(x, y) 두 정점 모두 (v1, v2)와 일치하지 않을 때 : 모순이다.

 

따라서, 임의의 정점이 항상 정답이라는 보장이 없으니 총 두 번의 탐색을 걸쳐 정답을 구해야 한다.

단, 별도의 조건이 없기에 하나로 이루어진 트리라 가정하고 풀이했다.

 

입력은 단방향 그래프로 주어지지만, 탐색을 위해 아래처럼 양방향 그래프 관계가 구성되어야 한다.

BFS 방식으로 풀이했다.

flag가 0이면, 올바른 정점 하나를 찾기 위한 로직을,

flag가 1이면, 시작점이 참임이 보장되기에 정답을 찾는 로직을 시행한다.

임의의 정점(v1)을 기준으로 연결된 모든 노드에 대해 탐색하며 가중치의 prefix sum을 visited 배열에 기록해 주었다.

물론, 초깃값(-1)이 아니면 재방문하지 않기에 가중치가 덮어씌워져 원래의 값보다 커지지 않는다.

모든 노드에 대한 탐색이 끝나면 임의의 시작점(start)으로부터 최대 가중치를 가지는 임의의 정점을 찾아야 한다.
몇 번 정점인지 확인해 보자.

이렇게 BFS(1)의 과정이 끝났다.
BFS(1)는 임의의 시작점인 1번 정점으로부터 최대 가중치를 가지는 올바른 정점 번호를 반환할 것이다.

하지만, 위에서 언급했듯 두 정점이 항상 참임이 보장되지 않기에 이전 탐색을 통해 얻은 올바른 정점번호를 시작점으로 BFS를 한 번 더 실행해 주어야 한다.

 

이번에는 정답(최대 가중치)을 구하는 로직이 필요하기에 다음과 같이 flag = 1로 실행하자.

---

소스코드

소스코드 보기

---

출처

1967번: 트리의 지름