(Python) [BOJ 1967] 트리의 지름

(Python) [BOJ 1967] 트리의 지름

문제: https://www.acmicpc.net/problem/1967

트리 내에 존재하는 모든 경로 중에서 가장 긴 경로를 찾고, 그 거리를 반환해야 하는 문제입니다.

이 문제에 처음 접근했을 때는 리프 노드들을 활용하는 것에 초점을 맞췄습니다. 한 리프 노드에서 다른 리프 노드로 가는 경로 중에 가장 긴 경로가 존재할 것으로 판단했기 때문입니다. 그래서 먼저 리프 노드들을 찾아내고 리프 노드 간 거리들을 계산하고자 했습니다.

하지만 왠지 이 방식이 비효율적인 것 같다는 느낌이 들어서 검색을 해봤더니 BFS(혹은 DFS) 두 번으로 이 문제를 해결할 수 있는 방법을 발견할 수 있었습니다. 해당 방법의 흐름은 다음과 같습니다.

먼저 특정 노드에서 가장 멀리 떨어진 노드(당연히 리프 노드)로 이동합니다. 그리고 그 노드에서 가장 멀리 떨어진 노드(이 역시 리프 노드)로 다시 한번 이동합니다. 해당(2번) 거리를 반환합니다.

이 방법을 사용하면, 기존 방식에서 리프 노드들을 찾아내는 과정을 생략할 수 있고, 흐름도 매우 깔끔해집니다 ㅠㅠ

import sys from collections import deque def get_dist(node): # BFS # SETTING visited = [-1] * (N + 1) # 방문 확인과 동시에 거리 저장 visited[node] = 0 q = deque([node]) while q: n_now = q.popleft() for n_next, weight in graph[n_now]: if visited[n_next] == -1: visited[n_next] = visited[n_now] + weight q.append(n_next) return visited.index(max(visited)), max(visited) # 가장 멀리 있는 노드, 그 거리 # 1. INPUT N = int(sys.stdin.readline()) graph = [[] * (N + 1) for _ in range(N+1)] # 무방향 for _ in range(N-1): n_start, n_end, weight = map(int, sys.stdin.readline().split()) graph[n_start].append((n_end, weight)) # 도착 노드, 가중치(거리) graph[n_end].append((n_start, weight)) # 2. BODY n_farthest, dist = get_dist(1) # 시작 노드 n_farthest, dist = get_dist(n_farthest) # 3. OUTPUT print(dist)

from http://sangdanghyunjeo.tistory.com/4 by ccl(A) rewrite - 2021-12-13 12:27:43