[파이썬/python] 백준 - 32985 트리 부수기

문제

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

---

문제 설명

1. 0번부터 N-1번까지 N개의 노드를 가진 트리가 주어진다.
2. 두 노드 u, v에 대하여 c(u,v)를 다음과 같이 정의한다.
   1. $f(x) = (c(x,N-1)c(x,N-2)...c(x,1))_{(2)}$
3. 이 때 $f(1)$ ⊕ $f(2)$ ⊕  $f(3)$...  ⊕  $f(N-1)$의 값을 구한다.

 

---

풀이

문제를 읽었을 때 XOR 비트를 구하는 거니까 당연히 비트마스킹을 쓰는 줄 알았다.

 

그런데 비트마스킹으로 풀려고 하다 보니 뭔가 시원하게 풀리지 않아서 예제 하나를 나열하고 하나의 규칙을 찾았다.

6
0 1
1 2
0 3
3 4
3 5

 

해당 예제에서 모든 경우의 수를 아래의 표에 전부 나열했다.

f(1,5) = 1	f(2,5) = 1	f(3,5) = 0	f(4,5) = 1	f(5,5) = 0
f(1,4) = 1	f(2,4) = 1	f(3,4) = 0	f(4,4) = 0	f(5,4) = 1
f(1,3) = 1	f(2,3) = 1	f(3,3) = 0	f(4,3) = 1	f(5,3) = 1
f(1,2) = 0	f(2,2) = 0	f(3,2) = 1	f(4,2) = 1	f(5,2) = 1
f(1,1) = 0	f(2,1) = 1	f(3,1) = 1	f(4,1) = 1	f(5,1) = 1

 

각각의 비트를 정리해보면

 

$f(1) = 11100_2$

$f(2) = 11101_2$

$f(3) = 00011_2$

$f(4) = 10111_2$

$f(5) = 01111_2$

으로 나타낼 수 있다. 이제 이 5개의 비트를 각각 XOR연산을 진행해야 한다.

 

여기서 만약 N이 200,000이라고 가정한다면 총 199,999개의 비트를 모두 XOR 연산을 진행해야 한다..

그렇기 때문에 결과를 도출할 수 있는 다른 방법을 찾아야 한다.

 

길이가 1인 비트들을 예시로 들어 XOR 연산을 진행해 보자.

 

XOR은 기본적으로 두 비트가 같으면 0, 다르면 1의 비트를 반환하는 계산이다.

따라서 0,0과 1,1은 0을 1,0과 0,1은 1을 반환한다.

 

5개의 비트를 1의 개수를 늘려가며 XOR 연산을 진행해 보자.

0 0 0 0 0 => 0

0 0 0 0 1 => 1

0 0 0 1 1 => 0

0 0 1 1 1 => 1

0 1 1 1 1 => 0

1 1 1 1 1 => 1

 

위에 결과를 보면 1이 늘어날수록 결괏값이 0과 1로 반복되는 규칙을 발견할 수 있다.

 

왜 그럴까?

 

0 0 1 1 1의 상황에서 1부터 순차적으로 XOR 연산을 진행해 보자.

0 0 1 (1 1) -> 0 0 (1 0) -> 0 (0 1) -> 0 1 -> 1, 결국 1이 1개만 남게 되어 남은 0들을 전부 1로 바꿔버린다.

 

그렇다면 반대로 0 1 1 1 1의 상황에서도 똑같이 진행시켜 보자.

0 1 1 (1 1) -> 0 1 (1 0) -> 0 (1 1) -> 0 0 -> 0, 1이 전부 사라지고 0밖에 남지 않았다.

 

(1 1)을 XOR 연산하면 0, 이를 다시 1과 XOR 연산하면 1, 0.. 1.. 0.. 1.... 이 계속해서 반복된다.

즉 1이 짝수개가 존재하면 0을 반환하고 1이 홀수개가 존재하면 1을 반환한다.

 

이 규칙이 이 문제의 핵심이다.

 

이제 문제에서 요구하는 XOR을 한 번에 구할 수 있다.

하지만 두 번째 문제는 각각의 $f(x)$값을 어떻게 구하느냐이다.

 

마찬가지로 1번 예제의 트리를 통해 예시를 들어보자.

해당 그림에서 각각의 $f(x)$ 값은 위에서 구했다.

그렇기에 값을 보고 한 가지를 판단할 수 있다.

 

$f(2) = 11101$

$f(4) = 10111$

$f(5) = 01111$

이 세 값의 공통점은 모두 리프 노드라는 것이다. 자식이 없기 때문에 해당 노드의 $f(x)$값은 해당 노드의 위치만 제외하고 모두 1의 값을 가진다.

 

$f(1) = 11100$이다. f(1)은 1과 2의 위치만 0이고 나머지는 모두 1이다. 왜 그럴까?

1은 자식으로 2를 보유하고 있기 때문에 1의 간선을 제거하면 1을 포함한 그 아래의 자식들도 전부 탐색이 불가능하기 때문이다.

 

그렇기 때문에 $f(3)$도 마찬가지로 자신의 자식을 포함해서 00011이라는 값을 가지는 것을 확인할 수 있다.(3,4,5가 0이다.)

 

이걸 통해 $f(x)$의 비트는 x가 루트인 서브트리에 포함되는 노드가 모두 0의 비트를 가진다는 것을 확인할 수 있다.

 

따라서 그래프 탐색을 통해서 노드를 탐색하며 비트를 만들어가면 된다.

나는 모든 비트를 따로 구하지 않고 해당 노드에서 몇 번째 비트가 1인지만 판단하고 전체 비트의 개수에서 빼는 방식을 채택했다.

 

예를 들면 이런 식이다.

노드가 총 5개이기 때문에 [5,5,5,5,5] 배열을 선언한다. 모든 노드의 비트가 1이라고 가정하는 것이다.

2번 노드를 탐색했을 때 값은 11101이다. 따라서 4번째 값이 0이기 때문에 4번 위치의 1의 개수를 1개 빼주는 식이다.

 

하지만 간과한 점이 하나 있다. 결국에는 서브트리의 상위 노드는 자식의 노드들도 모두 포함해야 하기 때문에,

1번 노드를 탐색할 때도 2번 노드의 값을 중복으로 제거해주어야 한다는 점이다.

 

이 부분은 그래프의 깊이와 연관이 있다. 0 - 1 - 2 - 3의 트리가 존재할 때 3은 (2 - 3)의 서브트리에도 존재하고 (1 - 2 - 3)의 서브트리에도 존재한다. 따라서 1번과 2번 노드에 방문했을 때도 각각 빼줘야 한다는 의미이다.

 

따라서 3까지 들어갔을 때의 깊이만큼 1을 빼주면 모든 서브트리의 3번 노드의 비트 값을 제거할 수 있다.

BFS를 통해 그래프를 탐색하고, 해당 노드의 깊이만큼 비트를 제거하여 결과를 출력했다.

 

1과 0의 개수를 통해서 결과를 도출할 수 있는 XOR연산의 특징을 미리 알고 있었다면 더 빠르게 문제를 풀 수 있었을 것 같다.

 

전에도 같은 유형의 문제를 풀었을 땐 잘 이해가 안 됐는데 직접 그려서 이해하니까 이해가 잘 된다. XOR 관련 문제 나오면 안 까먹고 잘 풀 수 있을 거 같다.

 

 

 

---

코드

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

N = int(input())
graph = [[] for _ in range(N)]

for i in range(N-1):
    v1,v2 = map(int,input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

def bfs():

    while queue:
        v1, depth = queue.popleft()
        res[v1] -= 1*depth

        for v2 in graph[v1]:
            if visited[v2]:
                continue

            visited[v2] = 1
            queue.append((v2,depth+1))
            

queue = deque([(0,0)])
res = [N-1 for _ in range(N)]

visited = [0 for _ in range(N)]
visited[0] = 1

bfs()

for i in list(reversed(res[1:])):
    print(1 if i % 2 == 1 else 0, end = '')

---

시간복잡도

• BFS의 시간복잡도는 $O(V+E)$ 따라서 약$O(4*10^5)$이다.

•