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

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

1967번: 트리의 지름

 

코드

import sys

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

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

def dfs(x, w):
    for i in graph[x]:
        a, b = i
        if distance[a] == -1:
            distance[a] = w + b
            dfs(a, w + b)

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

distance = [-1] * (n + 1)
distance[1] = 0
dfs(1, 0)

start = distance.index(max(distance))
distance = [-1] * (n + 1)
distance[start] = 0
dfs(start, 0)

print(max(distance))

 

문제를 읽고 말단 노드들로 dfs를 돌려서,

각 말단 노드 별로 최대 길이를 구하고

각각 구한 최대 길이들 중 최대 값을 구하면 될 것 같다고 생각했고,

생각한대로 구현하다가 뭔가 이상해서 실패함 ...

 

dfs의 분기 별 값을 비교해서 최댓값을 구하거나,

특정 조건에 카운팅을 해야 하는 경우에

카운팅 변수를 어떻게 해야 하는지에 대한 이해가 아직 확실하지가 않다.

 

global 키워드의 재귀 함수에서의 활용과

백트래킹 개념 및 코드 공부를 할 필요가 있다.

 

결국 다른 분들 코드를 참고했는데,

대부분의 사람들이 내 접근보다는

루트 노드에서 시작해 최대 길이가 나오는 끝 노드를 구하고

그 끝 노드에서 또 다시 최대 길이가 나오는 끝 노드를 구해서 트리의 지름을 구했다.

 

방문 여부를 확인하는 변수를 구하려는 값을 저장하는 변수로 활용하는 풀이도

더 익숙해질 때까지 연습할 필요가 있다.