BOJ 1167 트리의 지름 (Python)

문제풀이

가장 긴 경로를 찾는 방법과 관련된 아이디어가 필요한 문제로, 트리의 지름을 구하는 공식을 알면 쉽게 풀 수 있다.

가장 긴 경로 찾기 아이디어

아이디어: 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다.

트리의 지름은 임의의 두 노드 사이의 거리 중 가장 긴 것이라고 문제에서 정의하고 있다. 그러기 위해서 거리가 가장 긴 두 노드를 찾아야하는데, 모든 두 노드의 조합을 일일히 탐색해서 길이를 측정하면 시간이 초과된다.
하지만 가장 긴 경로 찾기 아이디어를 이용해 예를 들어 1번 노드를 탐색해서 가장 거리가 길게 나온 노드를 저장하고, 가장 길게 나온 노드를 탐색해서 가장 길이가 길게 나온 값을 출력하면 된다

풀이과정

과정 1: 그래프를 인접리스트로 저장해 (노드, 가중치)를 표현하기 위해 노드는 튜플로 선언하였다.

과정 2: 임의의 노드에서 BFS를 수행하고 탐색할 때 각 노드의 거리를 리스트에 저장

과정 3: 과정 2 에서 얻은 리스트에서 임의의 노드와 가장 먼 노드를 찾고 그 노드부터 BFS를 다시 수행

과정 4: 과정 3에서 거리 리스트에 저장한 값 중 가장 큰 값을 출력

Code

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

graph = [[] for _ in range(n+1)]

for _ in range(n):
    data = list(map(int,input().split()))

    start = data[0]

    for i in range(1, len(data)-2, 2):
        edge, cost = data[i], data[i+1]
        graph[start].append((edge, cost))

distance = [0] * (n+1)
visited = [False] * (n+1)

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i[0]]:
                queue.append(i[0])
                visited[i[0]] = True
                distance[i[0]] = distance[v] + i[1]

bfs(graph, 1, visited)
max = 1

for j in range(2, n+1):
    if distance[max] < distance[j]:
        max = j

distance = [0] * (n+1)
visited = [False] * (n+1)

bfs(graph, max, visited)

distance.sort(reverse=True)
print(distance[0])