[BOJ] 백준 15900번 나무 탈출 (Java)

#15900 나무 탈출

난이도 : 실버 1

유형 : 트리 / DFS 

15900번: 나무 탈출

▸ 문제

평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다.

'나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다.

이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나씩 놓여있는 채로 시작한다. 어떤 사람의 차례가 오면, 그 사람은 현재 존재하는 게임말 중 아무거나 하나를 골라 그 말이 놓여있던 노드의 부모 노드로 옮긴다. 이 과정에서 한 노드에 여러 개의 게임말이 놓이게 될 수도 있다. 이렇게 옮긴 후에 만약 그 게임말이 루트 노드에 도착했다면 그 게임말을 즉시 제거한다. 모든 과정을 마치면 다음 사람에게 차례를 넘긴다. 이런 식으로 계속 진행하다가 게임말이 게임판에 존재하지 않아 고를 수 없는 사람이 지게 된다.

성원이를 얕본 형석이는 쿨하게 이 게임의 선을 성원이에게 줘버렸다. 따라서 성원이가 먼저 시작하고 형석이가 나중에 시작한다. 그동안 형석이와 대결을 하면 매번 지기만 했던 성원이는 마음속에 분노가 가득 쌓였다. 이번 대결에서는 반드시 이겨서 형석이의 코를 꺾어주고 싶다. 그래서 게임을 시작하기 전에 게임판의 모양만 보고 이 게임을 이길 수 있을지 미리 알아보고 싶어졌다. 성원이가 이 게임을 이길 수 있을지 없을지를 알려주는 프로그램을 만들어 성원이를 도와주자.

▸ 입력

첫째 줄에 트리의 정점 개수 N(2 ≤ N ≤ 500,000)이 주어진다.

둘째 줄부터 N-1줄에 걸쳐 트리의 간선 정보가 주어진다. 줄마다 두개의 자연수 a, b(1 ≤ a, b ≤ N, a ≠ b)가 주어지는데, 이는 a와 b 사이에 간선이 존재한다는 뜻이다.

▸ 출력

성원이가 최선을 다했을 때 이 게임을 이길 수 있으면 Yes, 아니면 No를 출력한다.

 

문제 풀이  

트리와 게임이론의 개념을 합친 문제로, 성원이가 최선을 다했을 때 이길 수 있는 케이스를 알아낸 다음 DFS탐색을 통해 풀이할 수 있다.

 

구상

게임말은 단순 1칸씩 움직이고 1번 루트노드로 가면 사라진다. 성원이가 항상 선이기 때문에 움직일 수 있는 횟수가 총 짝수이면 무조건 지고 홀수이면 무조건 이긴다. 그러면 이젠 DFS탐색을 통해 해당 트리 구조에서 움직일 수 있는 횟수(각 리프노드 depth의 합)를 구하면 된다.

 

각 리프노드 depth의 합 구하기

 

주어지는 데이터는 꼭 부모노드 - 자식노드 순으로 주어지는 것이 아니기 때문에 탐색할 때 부모노드로 다시 거슬러 올라가지 않게끔 조건을 잘 설정해줘야 한다. (nxt != pa)

 루트노드를 제외한 연결된 노드 간선 갯수가 1개인 경우는 리프노드 밖에 없다. 그 중간 노드는 루트노드와 리프노드와 연결되어 있기 때문에 최소 간선이 2개이상이기 때문이다.  그러므로 각 리프노드의 depth를 합해주면 해당 게임에서 말을 움직일 수 있는 총 횟수를 구할 수 있다.

static void traversal(int idx, int pa, int depth){
	for(int nxt : list[idx]) {
		if(nxt != pa) {
			traversal(nxt, idx, depth+1);
		}
	}

	if(pa!=-1 && list[idx].size()==1) {
		cnt += depth;
	}
}

 

설계

1. 트리 데이터를 인접리스트 자료구조에 저장한다.
2. 1번 루트노드를 기준으로 dfs탐색을 한다. traversal(1,-1,0);
   1. 리프노드에 도달하면 해당 depth를 cnt에 합한다. cnt+=depth;
3. dfs탐색 종료 후 cnt(리프노드 depth의 합)이 짝수면 No, 홀수면 Yes를 출력한다. cnt%2==0 ? "No" : "Yes"

 

풀이 코드 

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

public class Main {

	static List<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());
		
		StringTokenizer st;
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		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);
		}
		
		traversal(1,-1,0);
        System.out.println(cnt%2==0 ? "No" : "Yes");
	}
	
	static void traversal(int idx, int pa, int depth){
		for(int nxt : list[idx]) {
			if(nxt != pa) {
				traversal(nxt, idx, depth+1);
			}
		}
		
		if(pa!=-1 && list[idx].size()==1) {
			cnt += depth;
		}
	}
}