[백준-파이썬] 1167: 트리의 지름

문제 보러 가기!

접근

전에 트리를 배우고 이 문제도 풀고 싶었다..
문제는 간단하지만 어떻게 풀지 몰랐다가 스터디에서 이 문제를 다뤘다.
트리의 지름을 찾고 싶으면, 임의의 정점 x를 잡고 거기에서 가장 먼 정점 y를 찾으라고 했다. 그리고 y에서 가장 먼 정점 z가 있을 텐데, y와 z 사이의 거리가 트리의 지름이라고 하셨다. 뭔가 수학적으로도 설명해주셨고 쉽게 원그림으로도 설명해주셨다.
원 안의 어떤 점 x를 잡고 거기에서 젤 먼 점 y를 잡으면 어떻게 될까? x에서 원의 중심을 지나서 원의 호가 y가 될 것이다. 그리고 y에서 가장 먼 점 z를 찾으면, 원의 어떤 호에서 중심을 지나서 다른 호로 갈 것이다. 그럼 그게 원의 지름이 된다.
이 아이디어를 구현해봤다!

코드

import sys

input = sys.stdin.readline

V = int(input())
adj = [[] for _ in range(V + 1)]

# 입력받기
for i in range(V):
tmp = list(map(int, input().split()))
curr_v = tmp [0]
adj_cnt = len(tmp) // 2 - 1
for j in range(adj_cnt):
adj_num, adj_distance = tmp[j * 2 + 1], tmp[j * 2 + 2]
adj[curr_v].append((adj_num, adj_distance))


def make_tree(curr_idx):
for a in adj[curr_idx]:
num, dis = a
if visited[num] == True:
continue
parent_list[num] = curr_idx
child_list[curr_idx].append((num, dis))
visited[num] = True
make_tree(num)





def visit(curr_node, curr_dis):
global max_distance, far_node
if curr_dis > max_distance:
max_distance = curr_dis
far_node = curr_node

for v, dis in child_list[curr_node]:
if check[v]==False:
check[v] = True
visit(v, curr_dis + dis)



# 트리의 지름
# 1. 임의의 정점 x 잡기(x가 루트라고 가정)
x = 1
parent_list = [0] * (V + 1)
child_list = list([] for _ in range(V + 1))
visited = [False] * (V + 1)
visited[x] = True
make_tree(x)

# 2. x에서 가장 먼 정점 y(dfs로 가장 아래까지..)
max_distance = -1
far_node = -1
check=[False]*(V+1)

visit(x, 0)
y = far_node
# print(far_node, max_distance)

# 3. y에서 가장 먼 정점 z
parent_list = [0] * (V + 1)
child_list = list([] for _ in range(V + 1))
visited = [False] * (V + 1)
visited[y] = True
make_tree(y)

max_distance = -1
far_node = -1
check=[False]*(V+1)
visit(y, 0)
# print(far_node, max_distance)


# y, z 사이의 거리가 트리의 지름이다.
print(max_distance)

소감

아이디어만 봤을 때는 간단할 줄 알았는데, 생각보다 길게 되었다..;;
다른 분들은 더 간단하고 빠르게 짜신 코드도 있는 것 같다.. 공부해 봐야지 !