[백준] 15900 나무 탈출 - 트리(Tree) + DFS + 트리의 성질 JAVA

https://www.acmicpc.net/problem/15900

15900번: 나무 탈출

코드설명

트리와 DFS를 활용하는 문제입니다.

 

문제의 예시대로 시뮬레이션을 해보면,

리프노드의 말을 하나씩 옮기다가 본인의 차례에 말이 남아있으면 지는 것이라는것을 알 수 있습니다. 

성원이가 게임을 먼저 시작하므로, 리프노드에서부터 루트노드까지의 거리를 DFS를 통해 전체를 구하면 거리가 나옵니다. 

그 거리가 홀수라면, 성원이가 이기고, 짝수라면 형석이 차례에 게임이 끝나게 되므로 성원이가 지게됩니다.

 

위의 로직대로 진행하면 됩니다.

유의해야할점은
아래의 코드에서 처음에 level 을 더하는것이 아닌 answer += 1을 함으로써 루트노드에서부터 리프노드까지의 depth를 더하지 않아서 틀렸었습니다.

if(start != 1 && graph.get(start).size() == 1) { //만약 리프노드면 한개만 연결되어있습니다.
    answer += level; //루트노드에서부터 리프노드까지의 거리 더하기
}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, Q;
	public static int[] arr;
	public static int answer = 0;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static boolean[] visited;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
    	

    	N = Integer.parseInt(st.nextToken());
    	visited = new boolean[N+1];
    	for(int i=0;i<=N;i++) {
    		graph.add(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());
    		graph.get(a).add(b);
    		graph.get(b).add(a);
    	}
    	
    	visited[1] = true;
    	DFS(1, 0);
    	
    	if(answer %2 == 1) System.out.println("Yes"); //전체 리프노드까지의 거리가 홀수면 먼저 옮긴사람은 다 옮길 수 있고, 두번쨰로 옮긴사람은 옮길것이 남아있으므로 성원이가 이깁니다.
    	else System.out.println("No");
    } 
    
    public static void DFS(int start, int level) {
    	
    	for(int i=0;i<graph.get(start).size();i++) {
    		int idx = graph.get(start).get(i);
    		if(visited[idx] == false) {
    			visited[idx] = true;
    			DFS(idx, level + 1);
    		}
    	}
    	
    	if(start != 1 && graph.get(start).size() == 1) { //만약 리프노드면 한개만 연결되어있습니다.
    		answer += level; //루트노드에서부터 리프노드까지의 거리 더하기
    	}
    	
    }
}