[baekjoon] 백준 1167번(파이썬): 트리의 지름

문제

1167번: 트리의 지름

알고리즘

- dfs 탐색을 통해 첫 번째 노드에서 제일 먼 노드를 찾는다.

- 첫 번째 노드에서 제일 먼 노드의 번호를 찾는다.

- 제일 먼 노드의 번호부터 다시 dfs 탐색을 통해 제일 먼 노드를 찾고 그때의 간선의 길이를 출력한다.

코드

import sys
sys.setrecursionlimit(10 ** 9)


# dfs 탐색
def dfs(x, y):
    # 각 노드와 연결된 노드를 확인
    for a, b in graph[x]:
        # 탐색하지 않은 노드라면
        if visited[a] == -1:
            visited[a] = b + y # 탐색하기까지 걸린 간선의 거리로 초기화
            dfs(a, b + y) # 재귀적으로 탐색


v = int(sys.stdin.readline())

# 각 노드의 연결된 정보를 트리로 표현
graph = [[] for _ in range(v + 1)]
for _ in range(v):
    w = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(w) - 2, 2):
        graph[w[0]].append([w[j], w[j + 1]])


visited = [-1] * (v + 1) # 탐색 여부, 간선의 거리
visited[1] = 0
dfs(1, 0) # 1번 노드에서 dfs 탐색

start = visited.index(max(visited)) # 1번 노드에서 제일 먼 노드를 찾는다.
visited = [-1] * (v + 1)
visited[start] = 0
dfs(start, 0) # 1번 노드부터 가장 먼 노드에서 다시 제일 먼 노드를 찾는다.

# 트리의 지름 출력
print(max(visited))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법