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

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

1967번: 트리의 지름

약 2주정도 고민했으나

도저히 안풀려서 결국 구글링을 했습니다.

제가 처음 잡았던 아이디어와 가장 유사한 것을 기준으로

코드를 참고했습니다.

우선, 그림으로 그려본 것입니다.

참고로 문제에서 주어진 트리는

이진트리가 아니지만

이해를 돕기 위해 이진트리로 그렸습니다.

저는 맨 위의 부모트리에서

아래로 차근차근 내려가는 방식을 구했습니다.

편의상 왼쪽 오른쪽 경로를 나눴는데,

이건 가장 긴 경로 2개를 나타냅니다.

부모노드를 기준으로

가장 먼 거 2개를 더해주면 트리의 지름이 나옵니다.

#백준 1967번 트리의 지름
import sys
sys.setrecursionlimit(10**6)
#recursion 에러를 막기위해 제안을 둔다

N=int(input())

graph=[[]for _ in range(N+1)]
#트리를 초기화킨다.
for _ in range(N-1):
    v1,v2,ga=map(int,input().split())
    graph[v1].append([v2,ga])


answer=0

#dfs로 트리 탐색
#왼쪽최장경로+오른쪽 최장경로의 합으로 구한다

def dfs(num,d):
    left,right=0,0
    now=graph[num]
    #현재의 노드에서 이어진 노드를 쭉 본다
    for to,cnt in now:
        r=dfs(to,cnt)
        
        if left<=right:
            left=max(left,r)
        else:
            right=max(right,r)

    global answer
    answer=max(answer,left+right)
    return max(left+d,right+d)

dfs(1,0)
print(answer)

 

https://my-coding-notes.tistory.com/285

[🥇4 / 백준 1967 / 파이썬] 트리의 지름

제가 참고한 코드입니다.

저는 왼쪽 오른쪽 구하는 것까지는 생각했으나

이걸 구현하는 게 잘 안되더라고요.

저는 부모노드를 기준으로

왼쪽 오른쪽을 더한다는 접근으로 하다보니

예시의 경우에서는 

부모노드를 기준으로

(왼쪽에서 최대)+(오른쪽에서 최대)

이런 값이 되어버리니

값이 예시로 나오지 않았습니다.

하지만 해당 코드의 방식은

answer를 전역변수로 두어서

모든 노드를 기준으로

왼쪽+오른쪽 경로를 더하고

계속 최댓값을 업데이트 해줬습니다.

https://velog.io/@bye9/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-1967-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84

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

https://kyun2da.github.io/2021/05/04/tree's_diameter/

[백준 / Python] 1967 트리의 지름 - Kyun2da Blog

다른 방식은

1. 부모로 부터 가장 멀리있는 노드와 길이를 구한다

2. 해당 노드로부터 가장 먼 거리의 노드와 길이를 구한다.

3. 두 길이를 합치면 그것이 트리의 지름이다.

 

라는 식으로 코드를 구성했습니다.

이 방식은 힌트로 많이 나왔으나

제가 초반에 이해가 안되서 넘겼던 방식이었는데

코드를 보니 어느정도 이해가 가더라고요.

코드의 정답은 없으니 여러분들이 편하신 방법으로

코드를 공부하시고

두 가지 방법 모두 다룰 줄 알면 퍼팩트!