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

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1167번: 트리의 지름

 

 

 

2. 문제 풀이

 트리의 양 끝단의 거리를 구하는 문제입니다. 즉, 트리에서 가장 먼 거리를 구해야 합니다.

 

2022.10.18 - [Algorithm] - [탐색/DFS] 백준 1967 트리의 지름 - 파이썬(Python)

 백준 1967문제와 동일하며, 입력 형식만 다릅니다. 어느 한 노드에서 가장 먼 노드를 구하고, 해당 노드에서 가장 먼 노드를 구하면 양 끝 노드를 찾을 수 있습니다.

 

 

 

3. 코드

import sys
sys.setrecursionlimit(10**9)  # dfs 반복횟수 제한 해제
input = sys.stdin.readline

# 입력
n = int(input())
graph = [[] for _ in range(n+1)]

for _ in range(n):
    node = list(map(int, input().split()))[:-1]
    for i in range(1, len(node)//2 + 1):
        graph[node[0]].append([node[i*2 - 1], node[i*2]])

# dfs
def dfs(x, dist):
    for i in graph[x]:
        node, wei = i
        if distance[node] == -1:
            distance[node] = dist + wei
            dfs(node, dist + wei)

# 1번 노드에서 가장 먼 곳을 찾음
distance = [-1] * (n+1)
distance[1] = 0
dfs(1, 0)

# 찾은 노드에서 가장 먼 노드를 찾음
res = distance.index(max(distance))
distance = [-1] * (n+1)
distance[res] = 0
dfs(res, 0)

# 출력
print(max(distance))

 총 dfs 탐색을 2번 사용해서 풀이합니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

dfs 탐색과 관련된 설명과 코드는 위 글에서 찾아보실 수 있습니다.