백준 24896번: 르블랑의 트리 순회
문제 링크
아이디어
순회가 불가능한 조건
1번 노드를 루트 노드로 트리를 순회한다고 가정했을 때, 한 번에 체크포인트가 3개 이상 필요하면 순회가 불가능하다.
위와 같은 트리는 순회가 가능하지만
위와 같은 트리는 순회가 불가능하다. 1번 노드의 오른쪽 서브 트리를 탐색한 후 왼쪽 서브 트리를 탐색하기 위해서는 루트 노드에 체크포인트를 생성해야 하는데, 오른쪽 서브 트리를 탐색하는데 체크포인트가 2개 필요하기 때문에 한 번에 체크포인트가 3개 필요하게 된다.
그렇다면 트리를 순회할 때 한 번에 필요한 체크포인트의 최대 개수는 어떻게 구할 수 있을까?
필요한 체크포인트의 개수 구하기
checkPoint[nodeNum]이라는 변수를 정의해보자. checkPoint[nodeNum]은 nodeNum번 노드를 루트 노드로 하는 서브 트리를 순회할 때 필요한 체크포인트의 최소 개수를 의미한다. checkPoint가 3 이상인 노드가 존재한다면, 그 트리는 순회가 불가능한 트리이다.
위에 나왔던 순회가 불가능한 트리의 checkPoint이다. checkPoint[1]이 3이므로 트리의 순회가 불가능하다.
이진 트리에서 checkPoint 구하기
이제 이진 트리에서 각 노드의 checkPoint를 구하는 방법을 생각해보자. checkPoint는 레벨이 높은 노드부터 구한다고 가정한다. 참고로 서브 트리의 checkPoint는 서브 트리의 루트 노드의 checkPoint를 의미한다. 정리하면 아래 세 가지와 같다.
- 서브 트리가 없는 경우 checkPoint는 0이다.
- 서브 트리가 한 개인 경우, 서브 트리의 checkPoint와 같다.
- 서브 트리가 두 개인 경우, max(checkPoint가 큰 서브 트리의 checkPoint, checkPoint가 작은 서브 트리의 checkPoint + 1)이다.
세 가지 경우에 대한 설명이다.
- 서브 트리가 없다는 뜻은 현재 노드가 리프 노드라는 뜻이고, 노드 한 개를 순회하는데는 체크포인트가 필요하지 않다.
- 서브 트리가 한 개인 경우 서브 트리를 순회하고 루트 노드로 돌아올 필요가 없으므로 서브 트리의 checkPoint와 같다. 루트 노드에서 바로 서브 트리로 이동해서 순회한다고 생각하면 된다.
- 양쪽 서브 트리를 다 순회하기 위해서는 한쪽 서브 트리를 순회한 후 다시 루트 노드로 돌아와야 한다. 이 경우에는 루트 노드에 체크포인트를 생성하고 시작해야 하기 때문에, 먼저 순회하는 서브 트리의 checkPoint + 1개의 체크포인트가 필요하다. 당연히 반대쪽은 서브 트리의 checkPoint개의 체크포인트가 필요하다. 우리는 checkPoint를 최대한 작게 만들어야 하기 때문에, 항상 작은 서브 트리를 먼저 순회하고 큰 서브 트리를 순회해야한다.
K진 트리에서 checkPoint 구하기
위에서는 쉽게 생각하기 위해 이진 트리에 대해서만 생각했지만, 주어진 문제는 이진 트리가 아니라 K진 트리이다. K진 트리에서는 3번 조건만 max(checkPoint가 가장 큰 서브 트리의 checkPoint, checkPoint가 두 번째로 큰 서브 트리의 checkPoint + 1)로 바꿔주면 된다. 결국 최댓값이 될 수 있는 후보는 첫 번째로 큰 서브 트리와 두 번째로 큰 서브 트리밖에 없기 때문이다.
구현
브루트 포스가 불가능한 이유
모든 노드의 checkPoint를 구하는 방법은 불가능하다. 루트 노드가 정해져 있지 않기 때문에, 모든 노드를 루트 노드로 했을 때 각각의 checkPoint를 알아내야 한다. checkPoint를 구할 때 시간 복잡도가 $O(N)$이라고 하면 모든 노드에 대해서 N번 실행해야 하므로 총 시간 복잡도는 $O(N^2)$이다. N이 최대 50만에 시간 제한이 2초이므로 당연히 TLE가 난다. 그래서 checkPoint가 0인 노드부터 지워나가는 방식으로 구현할 것이다.
checkPoint가 0인 노드 지우기
먼저 모든 리프 노드의 checkPoint는 0이므로 삭제할 수 있다. checkPoint의 최솟값이 0이므로, 서브 트리가 두 개 이상 존재하면 부모 노드의 checkPoint는 무조건 0보다 커지게 된다. 따라서 모든 리프 노드와 그 노드와 인접한 부모 노드 중 서브 트리가 하나인 노드들을 지워주면 된다.
처음 트리를 구성할 때 indegree 배열을 만들고 해당 정점에 간선이 연결될때마다 indegree 값을 1 더해준다. 트리가 전부 구성된 후 indegree 값이 1이면 그 노드는 리프 노드이고, 리프 노드와 연결된 노드 중 indegree 값이 2인 노드가 서브 트리가 하나인 부모 노드이다. 이 노드들을 삭제하면 된다.
위 과정을 한 번 반복하면 checkPoint가 0인 노드들이, 두 번 반복하면 checkPoint가 1인 노드들이 삭제된다. 여기서 말하는 checkPoint는 트리가 처음 구성되었을 때 기준이다. 두 번 반복해서 checkPoint가 1인 노드들까지 삭제했다고 생각해보자.
남아있는 노드들로 순회 가능여부 판단하기
남아있는 노드들은 checkPoint가 최소 2인 노드들이다. 이 노드들을 어떻게 배열하더라도 checkPoint가 3이상인 노드가 생길 수 밖에 없는 경우가 있다.
노드들의 indegree가 전부 2이하인 경우, 트리를 다시 배열해서 루트 노드의 checkPoint를 2이하로 유지할 수 있다.
하지만 indegree가 3이상인 노드가 존재하는 경우, 트리를 어떤 방식으로 재배열하더라도 루트 노드의 checkPoint가 3이상이 된다.
정리
- 트리를 구성한다.
- checkPoint가 0인 노드들을 삭제한다.
- checkPoint가 1인 노드들을 삭제한다.
- indegree가 3이상인 노드가 존재하면 “NO”, 존재하지 않으면 “YES”를 출력한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public class Main {
public static void main(String[] args) throws IOException {
Problem problem = new Problem();
problem.init();
problem.solve();
problem.getAns();
problem.printAns();
}
}
class Problem {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
int[] indegree;
boolean ans = true;
void init() throws IOException {
N = Integer.parseInt(br.readLine());
indegree = new int[N];
for(int i = 0; i < N; i++) {
graph.add(new ArrayList<Integer>());
}
for(int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken()) - 1;
graph.get(u).add(v);
graph.get(v).add(u);
indegree[u]++;
indegree[v]++;
}
}
void solve() {
for(int i = 0; i < 2; i++) {
deleteNode();
}
}
void deleteNode() {
Queue<Integer> q = new LinkedList<>();
Queue<Integer> deleteQ = new LinkedList<>();
boolean[] visited = new boolean[N];
for(int i = 0; i < N; i++) {
if(indegree[i] == 1) {
visited[i] = true;
q.add(i);
deleteQ.add(i);
}
}
while(!q.isEmpty()) {
int curNode = q.poll();
for(int i = 0; i < graph.get(curNode).size(); i++) {
int linkedNode = graph.get(curNode).get(i);
if(visited[linkedNode]) {
continue;
}
if(indegree[linkedNode] == 2) {
visited[linkedNode] = true;
q.add(linkedNode);
deleteQ.add(linkedNode);
}
}
}
while(!deleteQ.isEmpty()) {
int curNode = deleteQ.poll();
indegree[curNode] = 0;
for(int i = 0; i < graph.get(curNode).size(); i++) {
int linkedNode = graph.get(curNode).get(i);
indegree[linkedNode]--;
}
}
}
void getAns() {
for(int i = 0; i < N; i++) {
if(indegree[i] >= 3) {
ans = false;
return;
}
}
}
void printAns() throws IOException {
if(ans) {
bw.write("YES");
}
else {
bw.write("NO");
}
bw.flush();
bw.close();
br.close();
}
}