[Python/파이썬] 백준 1967 - 트리의 지름 (DFS / BFS)

문제 설명

 

입력과 출력

 

입출력 예제

# 입력
12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10

# 출력
45

 

 

---

풀이 코드

트리의 지름을 구하는 문제로, 가장 긴 이동 경로를 갖는 구간을 의미합니다.

트리의 지름을 구하는 방법은 다음과 같습니다.

1. 시작 정점에서 임의의 정점까지의 거리를 구하여 가장 먼 거리를 구합니다.

2. 1에서 찾은 가장 먼 거리를 시작 지점으로 하여 다시 한번 가장 긴 거리를 찾습니다.

 

정답 코드 (DFS)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())

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

for _ in range(n-1):
    p, c, d = map(int, input().split())
    tree[p].append((c, d))
    tree[c].append((p, d))

def dfs(start, distance):
    for next, next_d in tree[start]:
        if visited[next] == -1:
            visited[next] = distance + next_d
            dfs(next, distance + next_d)

# 시작 정점에서 임의의 정점까지의 거리를 구하고 그 중 가장 먼 거리를 구한다.
visited = [-1] * (n+1)
visited[1] = 0
dfs(1, 0)

# 위에서 찾은 노드에 대한 가장 먼 노드를 찾는다.
# 가장 먼 노드를 시작지점으로 하여 다시 한번 가장 긴 거리를 찾는다.
last_Node = visited.index(max(visited))
visited = [-1] * (n + 1)
visited[last_Node] = 0
dfs(last_Node, 0)

print(max(visited))

 

정답 코드 (BFS)

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    p, c, d = map(int,input().split())
    tree[p].append((c, d))
    tree[c].append((p, d))

def bfs(start):
    visited = [-1] * (n + 1)
    visited[start] = 0
    queue = deque()
    queue.append(start)
    
    while queue:
        cur = queue.popleft()
        for next, next_d in tree[cur]:
            if visited[next] == -1:
                queue.append(next)
                visited[next] = visited[cur] + next_d
    m = max(visited)
    return [visited.index(m), m]

print(bfs(bfs(1)[0])[1])