처음 구해본 트리의 지름 (골드3을 이해하기 시작하는 중)

#1167번 트리의 지름 https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

트리의 지름을 구하는 문제이다. 대충 거리의 총합정도는 구하겠는데 어떻게 최대거리를 갖는 노드를 찾는지 도저히 이해가 되지 않았다.

 

다음 블로그를 참고했다. https://blog.myungwoo.kr/112

트리의 지름 구하기

 

요약하면 이렇다

1. 트리의 임의의 한 정점 (x)에서 가장 긴 거리에 있는 정점 (a)을 구한다.

2. 그렇게 구한 정점 (a)에서 다시 가장 긴 거리에 있는 정점 (b)을 구한다.

3. a와 b 사이의 거리가 최대 거리 즉, 지름이 된다.

 

이해가 되는가?

import sys
# 재귀 제한 설정
sys.setrecursionlimit(100000)
input = sys.stdin.readline

# 입력받기
N = int(input())
graph = [[] for _ in range(N+1)]

for _ in range(N):
    tmp = list(map(int, input().split()))
    for i in range(1, len(tmp), 2):
        if tmp[i] == -1:
            break
        else:
            graph[tmp[0]].append([tmp[i], tmp[i+1]])
# print(graph)

# 그래프 깊이우선탐색
def dfs(node):
    for leef, dist in graph[node]:
        if visited[leef] == -1:
            visited[leef] = visited[node] + dist
            dfs(leef)

# 첫번째 실행 -> 임의의 노드에서 모든 노드까지의 거리 찾기
visited = [-1] * (N+1)
visited[1] = 0
dfs(1)
# print(visited)

# 이후 최대거리를 갖는 노드 찾기
max_node = [0, 0]
for idx in range(1, N+1):
    if visited[idx] > max_node[1]:
        max_node = [idx, visited[idx]]
# print(max_node)

# 두번째 실행 -> 최대거리 노드에서 다시 최대거리에 있는 노드 찾기
visited = [-1]*(N+1)
visited[max_node[0]] = 0
dfs(max_node[0])
# print(visited)

# 해당 길이가 정답
print(max(visited))

 

 

요즘들어 많이 쓰고있는 테크닉인데, 방문 탐색을 진행하는 visited를 기존에는 True, False로만 기록했었다.

하지만 이 리스트를 하나의 DP 리스트처럼 사용하는게 효율적이다.

 

초깃값을 설정하고, 방문시 값을 저장한다. 초깃값이 아닌 경우라면 방문한 노드이다.

( 초깃값은 그래프 탐색 연산에서 절대 나올 수 없는 값이어야 한다. 예를 들면 -1 같은.. )

 

위에서 제안한 방법의 증명은 블로그에 나와있다.

추가적으로 설명하면 이렇다

 

증명) 트리의 지름이 u, v라고 가정할 경우, 임의의 정점 x를 정하고, 가장 긴 정점 y를 찾았을 때를 아래와 같이 나눌 수 있다.

 

1. x가 u 혹은 v인 경우 (지름이 되는 정점 중 하나인 경우)

 -> 처음 시도했을 때 찾은 최대 길이의 정점 y

     x, y가 u, v 혹은 v, u가 된다. 아주 운이 좋은 케이스. 한번에 찾은거다.

 

2. y가 u 혹은 v인 경우

 x의 최대길이에 있는 정점y를 찾을 경우

다시 y의 최대길이에 있는 정점을 연산하기 때문에

y가 u인 경우에는 두번째 연산에서 v를 찾아낸다.

 

 

3. x,y,u,v가 서로 다른경우

 : 이 경우가 어렵다.

두 가지 경우로 나눌 수 있는데

 

a. x 와 y를 연결하는 경로가 정점 u와 정점 v를 연결하는 경로와 한 점 이상 공유하는 경우

 : 한 점을 공유할 때, 그 점을 t라고 하자.

x에서 가장 긴 정점이 y인 경우에

y-t의 거리 >= max(t-u의 거리, t-v의 거리)

가 되어야 한다.

 

모든 정점이 t를 거쳐가기 때문이다.

즉 u-v가 가장 긴 거리라는 가정에 모순이 생긴다.

존재할 수 없다.

 

b. 두 경로가 서로 독립인 경우

x에서 가장 먼 점이 v가 아니라 y라면,

u에서 가장 먼 점도 v가 아니라 y가 된다.

 

즉 논리적 모순이다.

존재할 수 없다.

 

 

 

위 논리를 종합하면 해당 방법이 트리의 지름을 올바르게 구한다는 사실을 알 수 있다.

 

사실 저 블로그에서 더 잘 증명했다고 생각한다.

 

알고리즘도 논리적 증명 과정이 필요하다는 사실을 처음 깨달았다.