[Algorithm] 백준 1967 - 트리의 지름 in Python(파이썬)

💡 백준 1967:

DFS 탐색을 통해 트리에서 가장 긴 거리 찾기

🌱 코드 in Python

알고리즘: DFS

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

n = int(input())
g = [[] for _ in range(n + 1)]
ret = 0
for _ in range(1, n):
	a, b, c = map(int,input().split())
	g[a].append((b, c))

def dfs(p, d):
	left, right = 0, 0
	for c, w in g[p]: # 자식이 있는 부모 노드의 경우
		tmp = dfs(c, w)
		if left <= right: # 첫번째 자식은 왼쪽 자식이 되어야 함
			left = max(left, tmp) # 왼쪽 자식에서 올라온 거리 갱신
		else:
			right = max(right,tmp) # 오른쪽 자식에서 올라온 거리 갱신
			
	global ret
	ret = max(ret, left + right) # 부모 노드에서의 최대 거리 갱신
	return max(left + d, right + d) # 두 자식까지의 거리에 자기 자신 거리 더해서 반환

dfs(1 , 0)
print(ret)

이번 문제는 트리의 최장거리를 찾는 문제였다

후.. 재귀라는 못풀겠구만 싶어서 바로 bfs로 갔는데.. dfs로 쌉 가능하지 모냐..

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
g = [[] for _ in range(n + 1)]

for _ in range(n - 1):
	p, c, w = map(int, input().split())
	g[p].append((c, w))
	g[c].append((p, w))

def bfs(i):
	visit = [0] * (n + 1)
	max = 0
	visit[i] = 1
	d = deque([i])
	while d:
		c = d.popleft()
		if i != c and len(g[c]) == 1:
			if max < visit[c]:
				max = visit[c]
			continue
		for p in g[c]:
			if not visit[p[0]]:
				visit[p[0]] = visit[c] + p[1]
				d.append(p[0])
	if max == 0:
		max = visit[c]
	return max - 1

ret = 0
max = 0
for i in range(1, n + 1):
	if len(g[i]) == 1:
		max = bfs(i)
	if ret < max:
		ret = max
print(ret)

내가 생각했던 하드코딩.. 맨 아래 자식노드에서 탐색하는 방식으로 했는데..
이라면 안되더라...
bfs로 하려면 부모에서 가장 먼 노드를 찾고 그 노드에서 가장 먼 노드를 찾는것이 답이란다..

난 정말 빡대가린가보다..
아직 잘 모르겠다....
더 많이 공부하는 수밖엔... ㅠ

🧠 기억하자

1. 재귀.. 너무 어렵당.. ㅠ

백준 1967 바로가기