[Python] 1167: 트리의 지름 (트리 지름의 성질, 귀류법 증명)

문제 링크

1167번: 트리의 지름

문제 요약

트리는 사이클 없이 모든 정점이 연결된 그래프이다. 정점의 갯수 V(1<=V<=10.0000)가 입력된 후, 각 정점별로 간선의 정보(연결 정점, 거리)가 입력된다. 한 정점에 연결된 간선은 여러 개일 수 있다. 이 때 트리의 지름을 구하라. 트리의 지름은 두 정점 간 거리의 최댓값이다.

풀이 설명

모든 정점 간의 거리를 구한 후, 최댓값을 얻는 방법

28분에 위의 초기 코드를 제출하였고, 결과는 메모리 초과였다. 이후, 구현한 코드가 플로이드-워셜 알고리즘이고 시간 복잡도도 계산했을 때, 플로이드-워셜 알고리즘과 마찬가지로 O(N^3), 공간 복잡도도 2차원 리스트가 10,000,000,000(100억) index의 공간을 차지해야하는데, Python에서 1차원 list가 2억 개 정도의 index까지 다룰 수 있다는 글을 보았을 때, 여러모로 문제 해결이 불가능한 코드이긴 하였다.

 

코드

import sys
input=sys.stdin.readline

V=int(input().rstrip())
graph=[[] for _ in range(V+1)]
for _ in range(V):
    row=list(map(int, input().rstrip().split()))
    start=row[0]
    for i in range(1, len(row), 2):
        if row[i]==-1:
            break
        elif row[i]>0:
            graph[start].append((row[i], row[i+1]))

dists=[[-1 for _ in range(V+1)] for _ in range(V+1)]
for i in range(1, V+1):
    dists[i][i]=0

for i in range(1, V+1):
    while graph[i]:
        end, dist=graph[i].pop()
        if dists[i][end]<dist:
            dists[i][end]=dist
            for j in range(1, V+1):
                if i!=j and dists[end][j]>0:
                    dists[i][j]=dists[i][end]+dists[end][j]

diameter=-1
for i in range(1, V+1):
    diameter=max(diameter, max(dists[i]))

print(diameter)

 

번외로, 이 문제보다 더 어려운 문제를 풀 수 있게 되면, 문제를 풀면서 새로운 풀이를 만들어볼 수도 있지 않을까, 그 풀이가 플로이드와 워셜 씨처럼 자신의 이름이 들어간 알고리즘이 될 수 있다는 사실에 굉장히 눈이 초롱해진다! (ㅋㅋㅋ) 🌟

 

시간 복잡도 O(N^3): 각각의 간선 정보 (start, end)에 대해 for i in range(N)로 순환하며, i!=end인 i를 찾아 [i][end]=[i][start]+[start][end]를 할당해야하고, 각각의 간선 정보는 N^2개 있으므로 시간복잡도는 O(N^3)이 된다.

트리 지름의 성질 활용한 풀이

위의 첫 번째 풀이를 생각하고. 구현해서 답 제출하는 데까지 28분 정도 걸렸고, 이후에 36분까지 메모리 초과+시간 초과를 해결할 방법을 고민해보았지만, 마땅한 아이디어가 생각나지 않아 답 코드를 검색하였다.

 

[백준 1167 파이썬] 트리의 지름 (골드 3, 트리)

 

풀이의 핵심은 트리의 성질을 활용하는 것이다. 그 성질은 아래와 같다.

임의의 정점에서 가장 먼 정점은, 트리 지름의 정점 중 하나이다.

 

이 성질을 활용하면, 가장 먼 정점을 찾고 (BFS 또는 DFS) 그 정점으로부터 가장 먼 정점을 찾아 그 거리를 출력하면 문제는 빠르게 해결할 수 있다.

 

코드

import sys
input=sys.stdin.readline
from collections import deque

V=int(input().rstrip())
graph=[[] for _ in range(V+1)]
for _ in range(V):
    row=list(map(int, input().rstrip().split()))
    start=row[0]
    for i in range(1, len(row), 2):
        if row[i]==-1:
            break
        elif row[i]>0:
            graph[start].append((row[i], row[i+1]))

def bfs(start):
    dists=[-1 for _ in range(V+1)]
    dists[start]=0
    visited=[0 for _ in range(V+1)]
    visited[start]=1
    q=deque([(start, 0)])

    while q:
        end, dist=q.popleft()
        for i in range(len(graph[end])):
            c_end, c_dist=graph[end][i]
            if visited[c_end]==0:
                if dists[c_end]<dists[end]+c_dist:
                    dists[c_end]=dists[end]+c_dist
                    q.append((c_end, dists[c_end]))
                    visited[c_end]=1
    
    max_dist=max(dists)
    diameter_node=[i for i in range(1, V+1) if dists[i]==max_dist][0]
    return diameter_node, max_dist


u, dist=bfs(start)
v, dist=bfs(u)
diameter=dist
print(diameter)

 

여기서 더 호기심이 생겼던 부분은 '어떻게 위의 성질을 증명할 수 있는가'하는 문제였다. 증명에는 여러가지 접근이 있었지만, 대체로 귀류법을 기반으로 증명하는 방법이 많았다.

귀류법은 어떤 명제의 부정이 거짓임을 증명하여, 원명제가 참임을 증명하는 논증 방법이다. 이외에 귀납법, 연역법과 같은 논증 방법이 있다.

이 포스팅을 참고하여 노트에 스스로 증명해보았다.

 

수학의 논증법, 이렇게 인간적인 예시에서 사용하니 이해가 잘 된다.