트리의 지름을 구하는게 공식이 있다니... (#1167)

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

 

문제를 풀이하는 과정이 너무 복잡했다. (결국 블로그 참고함)

 

다음 세 가지를 배울 수 있었다.

 

1. DFS 구현의 두 가지 방식(재귀 vs 스택)의 장단점

결론부터 말하면, 스택으로 구현해야 메모리를 덜 사용한다.

재귀로 짰더니 계속 메모리 초과가 났다.

 

2. 비트마스크로 visited를 처리하는 방법

기존의 리스트나 셋을 사용해서 노드 방문 여부를 체크하는 것과 달리 비트마스크로 구현하면 메모리 사용량을 줄일 수 있다.

쉽게 생각하면 기존에 [ 0, 1, 0, 1, 0, ... ] 이렇게 저장하던 visited 0/ 1을 그냥 붙여서 이진수로 표현하는 것이다.

Ob01010...

 

되게 심플하다.

따라서 원하는 인덱스 만큼 1을 밀어놓은 이진수를 OR 연산을 통해 visited값에 반영해주면 된다.

이진수를 몇 번 사용해본 사람이라면 금방 이해할 것이다.

 

https://wizdom.tistory.com/258

 

원소 추가는 or를 통해서 하고,

원소 조회는 and를 통해서 할 수 있다.

 

아주 심플하지만 효율적인 방법이다.

 

3. 트리의 지름을 구하는 공식

처음에는, dfs를 1부터 시작해서 제일 큰 누적 cost를 값으로 출력했다.

그랬더니 틀렸다.

 

생각해보면, 트리의 지름에 1번 노드가 포함되지 않을 수도 있다.

 

알아본 바로는, 

1. 1번 노드에서 제일 멀리 있는 노드를 찾는다.

2. 그 노드에서 제일 멀리 있는 노드까지의 cost를 구한다. -> 정답

 

이게 공식이라고 한다.

https://blogshine.tistory.com/111

 

어떻게 이해하면 좋을까.. 감은 잡히는데..

 

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

graph = {i : {} for i in range(1, n+1)}
# 리스트를 index로 관리해버리면, 인접 노드가 없는 노드에 대한 공간도 할당하기 때문에 메모리 초과가 난다.

for i in range(1, n+1):
    nums = list(map(int, input().split()))
    n = nums[0]
    nums = nums[1:-1]

    if len(nums) == 0:
        continue

    for j in range(0, len(nums), 2):
        graph[n][nums[j]] = nums[j+1]

# visited = [False for _ in range(n+1)]
# visited를 이진수로 처리한다고?? (비트마스크)
def dfs(start): # -> 재귀가 아니라 스택으로 바꿔야하나...
    visited = 0
    deep_dest = (None, -1) #node, cost
    stack = deque([(start, 0)])

    while stack:
        node, cost = stack.pop()
        visited |= (1<<node)
        if cost > deep_dest[1]:
            deep_dest = (node, cost)

        children = graph[node].keys()
        
        for v in children:
            if not (visited & (1 << v)):
                stack.append((v, cost + graph[node][v]))
                # visited &= ~(1<<v) 트리는 돌아갈 필요가 없다고..?
    return deep_dest

target = dfs(1)[0]
distance = dfs(target)[1]
print(distance)

# 배운점
## 1. DFS구현 시 재귀와 스택을 사용할 떄 발생하는 메모리 사용량 차이
## 2. 비트마스크로 visited 체크 하는 방법 (메모리 사용량 감소)
## 3. 트리의 지름을 구하는 공식 (증명 이해 필요)