[백준] 트리의 지름

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

1167번: 트리의 지름

dfs를 이용하는 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 

Tree의 정보가 주어지면, Tree 에서의  diameter를 구해야 하는 문제입니다. 실제로 문제를 한번 읽어보는 것을 추천합니다. 

 

Tree 자료구조란 

사이클이 없는 하나의 연결 그래프 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프) 의 한 종류라고 합니다. 

보통 diameter와 radius는 동일한 의미로 사용됩니다. 하지만 Tree에서는 다른 의미로 사용되는데, 위와 같이 트리의 지름 문제에서의 상황을 Tree의 diameter를 찾는다고 이야기를 합니다. 

 

Radius와 Diameter의 차이가 궁금한 사람은 

https://www.youtube.com/watch?v=04x5aGu6Oew 

동영상을 잠깐 보면 이해할 수 있습니다. 

 

이제 문제의 해결방법과, 그에 대한 간단한 정리를 해보려합니다. 

<Solution>

우선 핵심 아이디어는 다음과 같이 진행됩니다.

1. 임의의 node에서 가장 먼 node 찾기 2. 찾은 가장 먼 node를 출발지로 하는 가장 먼 node 찾기 3. 2번과정에서의 두 node 사이의 거리가 tree graph의 diameter가 된다.

이것이 왜 성립하는지 간단한 그림을 통해 생각해봅시다. (엄밀한 증명은 아니지만 생각자체만 해봅시다.)

다음과 같은 트리가 있다고 가정해 봅시다. 

이때, 다음과 같이 생각을 할 수 있습니다. 

따라서 2번 과정에서 찾은 node는 diameter를 구성하는 node중 하나일 것이고, 이 node에서 출발해서 가장 먼 node를 찾으면 이 두 node 가 diameter를 구성하는 node 두개가 될 것입니다. 

 

실제 구현은 아래와 같습니다. 

(dfs 과정이 두번 나오므로 실제 구현시 함수로 압축시키면 더 보기 좋은 코드가 될 것 같습니다. )

import sys
from collections import defaultdict
V = int(sys.stdin.readline().rstrip())

graph = defaultdict(list)

for _ in range(V):
    tmp = list(map(int,sys.stdin.readline().rstrip().split()))
    n_tmp = tmp[1:]
    for i in range(int((len(n_tmp)-1)/2)):
        graph[tmp[0]].append((n_tmp[2*i],n_tmp[2*i+1]))

# print(graph)

# dfs(from random node)
stack = [[1,0]]
visited = [False] * (V+1)
max_distance = 0
max_node = 0
while(stack):
    node, distance = stack.pop()
    # check max distance
    if distance > max_distance:
        max_distance = distance
        max_node = node
    if visited[node]:
        continue
    else: 
        visited[node] = True
    for n in graph[node]:
        if not visited[n[0]]:
            stack.append([n[0], distance+n[1]])

# print(f'max_node,max_distance = {max_node, max_distance}')

# dfs(from max_node)
stack = [[max_node,0]]
visited = [False] * (V+1)
max_distance = 0
max_node = 0
while(stack):
    node, distance = stack.pop()
    # check max distance
    if distance > max_distance:
        max_distance = distance
        max_node = node
    if visited[node]:
        continue
    else: 
        visited[node] = True
    for n in graph[node]:
        if not visited[n[0]]:
            stack.append([n[0], distance+n[1]])
# print(f'max_node,max_distance = {max_node, max_distance}')

print(max_distance)

<추가 (그냥 생각)>

무엇인가 random한 node를 뽑으면 그 node가 root가 되는 것처럼 생각해서 아이디어를 구상해 보아도 괜찮을 것 같다.