[백준 1167] 트리의 지름 - 파이썬(Python) BFS 풀이

트리의 지름

문제

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

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 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

11

---

너비 우선 탐색(BFS)

루트 노드에 바로 직접 인접한 분기들 먼저 전부 방문하고, 분기들의 직속 자식 노드들을 방문하는 방법입니다.

그래서 넓게 방문한다고 불립니다.

가장 인접한 노드들을 최우선적으로 방문하기 때문에 최단거리 구하는 문제에 적합합니다.

아래는 DFS로 탐색하는 순서입니다. 정점에 쓰여져 있는 숫자는 n번째, 즉 순서를 의미합니다.

 

BFS 구현

너비 후선 탐색은 큐로 구현할수 있습니다. 큐는 FIFO(First in, First out) 먼저 넣어준것을 먼저 출력하는 자료구조를 가지고 있습니다.

루트 노드에 가장 가까이 인접한 노드들을 먼저 입력해서 가장 인접한 노드들을 우선적으로 탐색합니다.

 

---

핵심 아이디어

"그래프에서 서로 가장 멀리 떨어져있는 두 노드는  임의의 한 노드에서 가장 떨어진 노드 중 하나이다"

 

트리의 지름은 임의의 두 노드 사이의 거리 중 가장 긴 것이라고 문제에서 정의하고 있습니다.

그려려면 거리가 가장 긴 두 노드를 찾아야하는데, 모든 두 노드의 조합을 일일히 탐색해서 길이를 측정하면 시간이 초과 됩니다.

 

그러나 핵심 아이디어를 이용하면 우리가 찾는 두 노드 중 하나를 찾을 수 있습니다.

예를 들어 1번 노드를 탐색해서 가장 거리가 길게 나온 노드를 저장하고, 그 노드를 또 탐색해서 가장 길이가 나온 케이스를 출력하면 됩니다.

---

파이썬 코드

distance[노드번호] 리스트에는 핵심노드로 부터 각 노드까지 걸리는 길이를 저장하는 곳입니다.

인접리스트(adjacent)에는 인접노드와 그 길이를 묶어서 튜플로 저장했습니다.

bfs 함수 내부에서, 만약에 i노드까지 가는 거리가 distance[i]라고 하겠습니다.

i노드의 인접한 노드의 번호가 j이고 엣지의 길이가 b라고 하겠습니다. -> 인접리스트에서 (j , b) 라고 저장되어있겠죠?

j는 i를 경유해야만 갈수 있는 곳이므로 j까지 가는 거리는 distance[i]+b가 되고 distance[j]에 저장되는 것입니다.

distance 리스트에서 가장 높게 나온 인덱스번호(노드)가 우리가 구하는 노드중하나 입니다.

그 노드에 대해서 탐색을 하고, 최대거리를 트리의 지름으로 출력합니다.

# BFS GOLD2

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
visited = [False]*(n+1)
adjacent = [ [] for _ in range(n+1) ]

for i in range(1,n+1):
    req = list(map(int , input().strip().split()))
    index = 0
    S1 = req[index]
    index+=1
    while True:
        S2 = req[index]
        if S2 == -1:
            break
        E = req[index+1]
        adjacent[S1].append((S2,E))
        index+=2

distance = [0] * (n+1)

def bfs(start):
    queue = deque()
    queue.append(start)
    visited[start]=True
    while len(queue)!=0:
        node = queue.popleft()
        for i in adjacent[node]:
            if visited[i[0]] == False:
                queue.append(i[0])
                visited[i[0]]=True
                distance[i[0]]= distance[node]+i[1]

bfs(1)
result_index = distance.index( max(distance) )
visited = [False]*(n+1)
distance = [0] * (n+1)
bfs(result_index)
print(max(distance))