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

문제 설명

 

입출력 예제

# 입력
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

# 출력
11

 

---

풀이 코드

이전 포스팅한 백준 1967 트리의 지름 문제와 별 차이가 없습니다.

주어진 입력값으로 그래프를 초기화하는 방법만 다를 뿐입니다.

 

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

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

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

 

정답 코드 (DFS)

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

V = int(input())
graph = [[] for _ in range(V + 1)]

for _ in range(V):
    info = list(map(int, input().split()))
    for n in range(1, len(info) - 2, 2):
        graph[info[0]].append((info[n], info[n + 1])) # (연결노드, 거리)

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

visited = [-1] * (V + 1)
visited[1] = 0
dfs(1, 0)

last_Node = visited.index(max(visited))
visited = [-1] * (V + 1)
visited[last_Node] = 0
dfs(last_Node, 0)

print(max(visited))

 

정답 코드 (BFS)

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

V = int(input())
graph = [[] for _ in range(V + 1)]

for _ in range(V):
    info = list(map(int, input().split()))
    for n in range(1, len(info) - 2, 2):
        graph[info[0]].append((info[n], info[n + 1])) # (연결노드, 거리)

def bfs(start):
    visited = [-1] * (V + 1)
    visited[start] = 0
    q = deque()
    q.append(start)

    while q:
        cur = q.popleft()
        for next, next_d in graph[cur]:
            if visited[next] == -1:
                q.append(next)
                visited[next] = visited[cur] + next_d
    
    m = max(visited)
    return [visited.index(m), m]

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