문제
루트가 1인 트리가 주어질 때, 모든 리프 노드의 깊이 합이 홀수이면 "Yes", 짝수이면 "No"를 출력하라. 성원이와 형석이가 번갈아 리프 노드의 간선을 하나씩 제거하는 게임에서 성원이(선공)의 승리 여부를 판별한다.
입력
첫째 줄에 노드 수 N, 이후 N-1개의 간선이 주어진다.
출력
성원이가 이기면 "Yes", 지면 "No"를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 1 2 2 3 3 4 1 5 | Yes |
풀이
DFS로 모든 리프 노드의 깊이 합을 구하고, 홀짝을 판별한다.
- 인접 리스트로 트리를 구성한다
- 루트(1번)에서 DFS를 시작하며 깊이(cnt)를 누적한다
- 리프 노드(자식이 없는 노드, 즉 인접 노드가 부모뿐인 노드)에 도달하면 깊이를 ans에 더한다
- 전체 합이 홀수이면 "Yes", 짝수이면 "No"를 출력한다
핵심 아이디어: 게임의 총 이동 횟수는 모든 리프의 깊이 합과 같다. 홀수면 선공 승리, 짝수면 후공 승리이다.
코드
package day449;
import java.io.*;
import java.util.*;
public class Day414BOJ15900나무탈출 {
static int ans = 0;
static List<Integer>[] list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
list = new LinkedList[N + 1];
for (int i = 1; i <= N; i++) {
list[i] = new LinkedList<Integer>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list[a].add(b);
list[b].add(a);
}
dfs(1, 0, 0);
System.out.println((ans % 2) == 0 ? "No" : "Yes");
br.close();
}
public static void dfs(int cur, int p, int cnt) {
for (int next : list[cur]) {
if (next != p) {
dfs(next, cur, cnt + 1);
}
}
if (list[cur].size() == 1) {
ans += cnt;
}
}
}복잡도
- 시간: O(N)
- 공간: O(N)