[백준] 1167번, 트리의 지름 | (python,파이썬)

문제 링크

 

1167번: 트리의 지름

---

문제

---

문제해결하기

 트리의 지름 ?

트리의 지름이란 가장 먼 두 정점 사이의 거리, 연결하는 경로를 의미한다. 쉽게 얘기하면, 트리 내의 임의의 두 정점사이의 거리가 가장 길때, 그 길이가 트리의 지름이다. 그러면 트리의 지름은 어떻게 구할까 ?

 

i. 트리에서 임의의 정점을 정한다

ii. 위에서 택한 임의의 점 하나에서 가장 거리가 먼 정점 a를 찾는다.

iii. 정점 a에서 가장 거리가 먼 정점, 그 길이가 트리의 지름이다.

---

 ○간선의 정보를 입력할때, 정점들의 정보를 저장하는 리스트 G에 [정점, 정점과의 거리]처럼 리스트로 묶어 정보를 저장했다.

 

 ○거리의 정보를 저장할 리스트 distance를 마련해여 DFS를 재귀적으로 진행하면서, 임의로 설정한 정점과 방문중인 정점의 거리의 정보를 distance에 업데이트 해주었다.

 

 ○ 임의의 점으로 DFS를 한번 실행 후 임의의 점과 가장 긴 거리에 있는 정점을 찾아, 그 정점으로 DFS를 실행한다! 

→ 정점의 정보들을 순차적으로 저장했기 때문에, distance의 최대값 index가 바로 우리가 찾는 정점이다.

 

---

정답코드

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

def DFS(G, v):
    visited_D[v] = True
    d = distance[v] #임의 설정한 정점과 현재 방문중인 정점과의 거리
    for w in G[v] :
        if visited_D[w[0]-1] == False : 
            distance[w[0]-1] = w[1]+d
            DFS(G,w[0]-1)    

n = int(input())
G = [[] for _ in range(n)]
distance = [0 for _ in range(n)]

for _ in range(n) :
    a = list(map(int,input().split()))
    for i in range(1,len(a)-1,2) :
        if i == -1 : break
        G[a[0]-1].append([a[i],a[i+1]])

visited_D = [False]*n
DFS(G,0) #임의의 점을 0으로 잡고, DFS

k = distance.index(max(distance)) #가장거리가 먼 정점 저장
distance = [0 for _ in range(n)] #DFS를 한번 더하기 위해 초기화
visited_D = [False]*n #DFS를 한번 더하기 위해 초기화
DFS(G,k)
print(max(distance))