개념
m개의 노드로 구성된 트리가 있고, 각 노드에는 하나의 값이 연결되어 있다고 가정해 봅시다. 이때 임의의 간선을 끊으면 트리가 분리되어 두 개의 새로운 트리가 만들어집니다. 우리가 구해야 할 것은, 특정 간선을 끊었을 때 분리된 두 트리에 속한 노드 값들의 비트 OR(Bitwise OR) 결과가 서로 같아지도록 만들 수 있는 그런 간선의 개수입니다. 단, 모든 노드의 값은 10^6 이하라고 가정합니다.
입력 예시
values[] = {1, 3, 1, 3}
1
/ | \
2 3 4출력 예시
2
위 예제에서는 노드 1과 노드 2 사이의 간선을 끊으면, 분리된 두 트리 각각의 비트 OR 결과가 3으로 동일해집니다.
마찬가지 방식으로 노드 1과 노드 4 사이의 간선도 조건을 만족하므로, 정답은 총 2개의 간선이 됩니다.
풀이 방법
이 문제는 간단한 DFS(깊이 우선 탐색)를 활용하여 해결할 수 있습니다. 노드의 값이 10^6 이하이므로 최대 22개의 이진 비트로 표현할 수 있고, 따라서 여러 노드 값의 비트 OR 결과 역시 22비트 안에서 표현 가능합니다.
핵심 아이디어는 다음과 같습니다. 각 서브트리에 대해, 해당 서브트리 내 노드 값들 중 각 비트(0번부터 21번까지)가 설정(set)되어 있는 노드의 개수를 미리 계산해 둡니다. 그런 다음 각 간선에 대해, 그 간선을 기준으로 나누어진 두 트리에서 각 비트별로 '그 비트가 설정된 노드 수'를 비교합니다. 만약 모든 비트에 대해 두 트리 모두에서 해당 비트의 개수가 0이거나, 양쪽 모두 0보다 크다면, 두 트리의 비트 OR 결과는 같다는 의미이므로 해당 간선을 정답에 포함시킵니다.
C++ 구현 예제
// C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
int m1[1000], x1[22];
// a1[i][j] : i번 노드를 루트로 하는 서브트리에서 j번 비트가 설정된 값의 개수
int a1[1000][22];
vector<vector<int>> g;
int ans1 = 0;
// 간단한 DFS 수행 함수
void dfs(int u1, int p1){
for (int i = 0; i < g[u1].size(); i++) {
int v1 = g[u1][i];
if (v1 != p1) {
dfs(v1, u1);
// v를 루트로 하는 서브트리의 비트 정보를 부모에게 누적
for (int i = 0; i < 22; i++)
a1[u1][i] += a1[v1][i];
}
}
// 각 비트마다 두 트리에서 해당 비트가 설정된 개수가
// 둘 다 0이거나, 둘 다 0보다 큰지 검사
int pp1 = 0;
for (int i = 0; i < 22; i++) {
if (!((a1[u1][i] > 0 && x1[i] - a1[u1][i] > 0)
|| (a1[u1][i] == 0 && x1[i] == 0))) {
pp1 = 1;
break;
}
}
if (pp1 == 0)
ans1++;
}
// 드라이버 코드
int main(){
// 노드 개수
int n1 = 4;
// 트리 구조 저장용 벡터
g.resize(n1 + 1);
// 노드 값 저장
m1[1] = 1;
m1[2] = 3;
m1[3] = 1;
m1[4] = 3;
// 전체 트리에서 각 비트가 설정된 횟수 계산
for (int i = 1; i <= n1; i++) {
int y1 = m1[i];
int k1 = 0;
// i번 노드 값의 설정된 비트 확인
while (y1 != 0) {
int p1 = y1 % 2;
if (p1 == 1) {
x1[k1]++;
a1[i][k1]++;
}
y1 = y1 / 2;
k1++;
}
}
// 간선 추가
g[1].push_back(2);
g[2].push_back(1);
g[1].push_back(3);
g[3].push_back(1);
g[1].push_back(4);
g[4].push_back(1);
dfs(1, 0);
cout << ans1;
}실행 결과
2
코드 설명 및 시간 복잡도
위 코드의 동작 과정을 요약하면 다음과 같습니다.
1단계 - 초기화: 전체 트리에서 각 비트가 설정된 노드의 총 개수를 배열 x1에 기록하고, 동시에 각 노드 자신의 값을 기준으로 a1 배열을 초기화합니다.
2단계 - DFS 탐색: 루트(노드 1)부터 DFS를 수행하며, 자식 서브트리의 비트 카운트를 부모 노드로 누적합니다. DFS가 노드 u에서 돌아오는 시점에는 a1[u]에 'u를 루트로 하는 서브트리'의 비트 정보가 완성됩니다. 이때 간선 (u, 부모)를 자르면 한쪽 트리는 u의 서브트리가 되고, 다른 쪽 트리는 나머지 부분이 되므로, 두 트리의 비트 정보를 바로 비교할 수 있습니다.
3단계 - 조건 검사: 각 비트 i에 대해 a1[u1][i](한쪽 트리)와 x1[i] - a1[u1][i](다른 쪽 트리)를 비교하여, 모든 비트에서 두 값이 동시에 0 또는 동시에 양수인 경우 ans1을 증가시킵니다.
시간 복잡도는 각 노드마다 22개 비트를 검사하므로 O(N × 22), 즉 노드 수에 대해 선형 시간이며 공간 복잡도는 O(N × 22)입니다.