[백준 1967번][Python] - 트리의 지름

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

 

 

 

 

# 풀이과정

트리의 지름은 가장 거리가 먼 두 노드 사이의 거리이다. 그렇다면 그 두 노드를 어떻게 구해야 할까?

정답은 간단하다. 아래의 세 단계의 과정을 거치면 된다.

1. 임의의 한 노드에서 가장 거리가 먼 노드를 구한다. 해당 노드를 V라고 한다.
2. V에서 가장 먼 노드를 구한다. 해당 노드를 N이라고 한다.
3. V와 N사이의 거리가 곧 트리의 지름이다.

 

 

[DFS를 이용한 코드 - 성공]

# ex_1967
import sys
sys.setrecursionlimit(100000)
n = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a].append((b,c))
    graph[b].append((a,c))
visited = [0 for _ in range(n+1)]	# 방문여부확인
distance = [0 for _ in range(n+1)]	# 거리를 저장하는 배열

def dfs(start,d):
    distance[start] = d
    for sub in graph[start]:    # sub[0]:목적지, sub[1]:거리
        if visited[sub[0]] == 0:
            visited[sub[0]] = 1
            dfs(sub[0],d+sub[1])
            visited[sub[0]] = 0

# 루트 노드에서 가장 먼 노드 정하기
visited[1] = 1
dfs(1,0)
visited[1] = 0

v = distance.index(max(distance))	# v:루트 노드로부터 가장 먼 노드
distance = [0 for _ in range(n+1)]

# v로부터 가장 먼 거리 구하기
visited[v] = 1
dfs(v,0)

print(max(distance))