[트리의 지름] 백준 1167 | BFS | 파이썬

GaShine·2024년 5월 6일

baekjoon python 백준

Algorithms

목록 보기

10/13

문제

백준 - 트리의 지름

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제 입력1

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

예제 출력1

풀이

BFS로 풀었다. 처음엔 인접한 노드들의 거리를 비교해서 가장 먼 거리를 선택하려고 했지만 다음과 같은 예시로 올바르지 못함을 느꼈다.

문제에서는 V=5까지 나왔지만, 만약 위와 같은 상황이라고 가정해보자.
노드4에서 인접한 노드 2와 5 중 거리가 6으로 더 먼 노드5를 선택하면, 최종적으론 노드4에서 노드6까지 거리는 7이고 노드4에서 노드7까지 거리는 14로 최장거리를 구할 수 없다.

그래서 모든 길을 다 탐색하되, 최장 거리를 리턴해주는 걸로 구현했다.

하지만 이를 V번 했다는 거..

for i in range(1, V + 1):
    answer = max(answer, bfs(i, 0))
    visited = [False] * (V + 1)

제출하면서도 너무 비효율적인데.. 이 생각을 했다.

검색을 해보니

트리에서 임의의 노드에서 최대 거리에 있는 노드는 반드시 트리의 지름의 양 끝점 중 하나이다.
즉 임의의 점 (A)에서 가장 먼 지점 B를 찾은 후, B에서 가장 먼 지점 (C)를 찾으면 트리의 지름은 B-C가 된다.

이와 같은 공식으로 효율적으로 풀 수 있다.
이 공식에 대한 증명은 ji.o.n.e님께서 잘 정리해주셨다. 😊

그래서 풀이는

가장 먼 거리의 지점과 거리를 리턴하는 bfs() 구현
아무지점에서 bfs() 함수 호출하여 가장 먼 거리의 지점과 거리 구함
2에서 구한 지점에서 bfs() 함수를 호출하여 가장 먼 거리의 거리를 구함

코드

# 트리의 지름

from collections import deque
import sys

input = sys.stdin.readline
V = int(input())

graph = [[] for _ in range(V + 1)]
visited = [False] * (V + 1)

for _ in range(V):
    inputList = list(map(int, input().split(' ')))
    s = inputList[0]

    for i in range(1, len(inputList) - 2, 2):
        graph[s].append((inputList[i], inputList[i + 1]))


def bfs(start, distance): # 1. 가장 먼 거리의 지점과 거리를 리턴하는 bfs() 구현
    myque = deque()

    visited[start] = True
    myque.append((start, distance))

    res = [0, 0]

    while myque:
        now, ndistance = myque.popleft()
        if res[1] < ndistance:
            res[1] = ndistance
            res[0] = now

        for next, dis in graph[now]:
            if not visited[next]:
                visited[next] = True
                myque.append((next, ndistance + dis))

    return res


far_edge, _ = bfs(2, 0) # 2. 아무지점에서 bfs() 함수 호출하여 가장 먼 거리의 지점과 거리 구함
visited = [False] * (V + 1) # 초기화
_, answer = bfs(far_edge, 0) # 3. 2에서 구한 지점에서 bfs() 함수를 호출하여 가장 먼 거리의 거리를 구함

print(answer)