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

문제:www.acmicpc.net/problem/1967

1967번: 트리의 지름

import sys
from collections import deque
N=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,val=map(int,sys.stdin.readline().rstrip().split())
    graph[a-1].append([b-1,val])
    graph[b-1].append([a-1,val])

def bfs(start,mode):
    q=deque()
    val=[-1]*N
    val[start]=0
    q.append(start)
    while q:
        dot=q.popleft()
        for x in graph[dot]:
            if val[x[0]]==-1:
                val[x[0]]=x[1]+val[dot]
                q.append(x[0])
    
    if mode==1:
        return val.index(max(val))
    else:
        return max(val)

print(bfs(bfs(0,1),2))

 

 

참고:https://chldkato.tistory.com/29

백준 1967 트리의 지름 (파이썬)

문제 접근은 최대길이가 되는 좌표를 찾아낸다. 그리고 그 좌표로부터 거리가 최대가 되는 것을 찾는다.

mode 1이 이제 루트로부터 거리가 최대인 좌표를 찾는 것이다.

mode 2는 최대인 좌표로부터 거리가 제일 큰 좌표를 찾는 것이다.

 

다른 풀이도 설명해보려 한다.

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def dimt(idx):
    global R
    if tree[idx]:
        large = 0
        small = 0
        for i, d in tree[idx]:
            now_distance = dimt(i)+d
            if now_distance > large:
                small = large
                large = now_distance
            elif now_distance > small:
                small = now_distance
        R = max(large + small, R)
        return large
    else:
        return 0


N = int(input())
tree = [[] for _ in range(N+1)]
N -= 1
R = 0
while N:
    parent, child, distance = map(int, input().split())
    tree[parent].append([child, distance])
    N -= 1
dimt(1)
print(R)

 

 

참고: 백준 파이썬 상위권 코드