[백준 1967번 트리의 지름] 파이썬 풀이

 

이 문제는 골드 4이지만 DFS만 구현할줄 아시면 바로 풀 수 있는 문제입니다.

 

우선 정답 코드입니다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

def DFS(node,weight):
    for nxt, we in tree[node]:
        if visited[nxt] == -1:
            tmp = weight + we
            visited[nxt] = tmp
            DFS(nxt,tmp)
    return



N = int(input().strip())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,w = map(int,input().strip().split())
    tree[a].append((b,w))
    tree[b].append((a,w))

visited = [-1] * (N+1)
visited[1] = 0
DFS(1,0)

idx = visited.index(max(visited))


visited = [-1] * (N+1)
visited[idx] = 0

DFS(idx,0)
print(max(visited))

 

구조는 간단합니다. 트리구조에 가중치를 저장하기 위해 입력을 받고

 

그 후 DFS를 통해 루트 노드로부터 가장 거리가 큰 노드를 찾습니다.

 

그 후 그 노드부터 가장 멀리떨어진 즉 거리가 큰 노드를 찾습니다.

 

def DFS(node,weight):
    for nxt, we in tree[node]:
        if visited[nxt] == -1:
            tmp = weight + we
            visited[nxt] = tmp
            DFS(nxt,tmp)
    return

 

여기서 노드와 가중치를 받아와서 그 노드와 연결되어있는 노드와 가중치를 받아옵니다.

그런 뒤에 방문한적이 없는 노드면 

지금까지 더해져온 거리와 새로 받아온 노드의 가중치를 더해 저장합니다.

그 뒤에 그 노드와 연결된 노드가 있는지 DFS를 재귀로 구현합니다.

 

이게 왜 가능하냐면 트리의 구조 때문입니다.

A로부터 B로 가는 길은 결국 한가지 경우 밖에 없기 때문에 방문을 한번만 할 수 밖에 없는 구조입니다 ㅎㅎ

다시 B에서 A로 올라오는 경우를 제외하면 말이죠 ! 

그래서 visited를 초기에 -1로 설정을 해둡니다.

 

아 그리고 문제 제출할때 런타임에러나시는분들은

 

sys.setrecursionlimit(100000000)

이거 한줄 추가하시면 accept될겁니다.