[JAVA] 백준 15900 : 나무 탈출

문제

15900번: 나무 탈출

 

해결 방법

천천히 문제를 읽어보고 주어진 입력을 손으로 그려보았다.

그 결과 알 수 있는 점은 모든 리프 노드에서 루트 노드까지 거리가 홀수일 경우 성원이가 이길 수 있고,

짝수일 경우 성원이가 질 수밖에 없음을 알 수 있다.

 

예제 입력 2를 그림판으로 그려본 것인데, 게임 말은 리프노 노드에 위치한다고 했기 때문에

3 과 4에서 시작한다. 각각 2와 1을 거쳐 2칸, 2칸, 즉 총 4칸을 움직여야 모든 게임 말이 제거된다.

그렇기 때문에 모든 리프 노드에서 루트 노드까지의 거리 = 게임 말이 움직이는 횟수 가 되고

4칸은 짝수이기 때문에 성원이가 질 수 밖에 없다. (게임은 무조건 성원이가 먼저 시작하기 때문)

 

결국, 모든 리프 노드에서 루트 노드까지의 거리를 합한 다음 짝수인지 홀수인지만 판별하면 해결할 수 있다.

 

코드는 인접리스트를 구현한 뒤에 dfs를 통해 방문하는데, dfs는 탐색을 시작하는 위치와 부모의 값, 깊이를 받는다.

리프 노드에 도달하면 그곳까지의 깊이를 cnt에 더해주어 모든 리프 노드에서 루트 노드까지의 거리를 계산했다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {
	static ArrayList<Integer> list[];
	static int cnt = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		list = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<>();
		}
		
		StringTokenizer st;
		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, -1, 0); // 1이 루트 노드이기 때문에 부모가 없어 -1로 부여.
		
		if (cnt % 2 == 1) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
	
	static void dfs(int start, int parent, int depth) {
		// 방문 확인용 배열을 따로 만들어도 되지만 부모 노드의 값을 입력받아
		// 불일치 여부를 통해 dfs 탐색을 진행할 수도 있다.
		
		boolean isLeaf = true; // 리프 노드 확인용.
		
		for (int next : list[start]) {
			if (next != parent) {
				dfs(next, start, depth + 1);
				isLeaf = false; // 아직 갈 수 있는 곳이 있다면 리프 노드가 아님.
			}
		}
		
		if (isLeaf) cnt += depth; // 리프 노드라면 깊이(거리)를 더해줌.
	}
}