[BOJ 15900] 나무 탈출 (Java)

#문제

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

15900번: 나무 탈출

#풀이

Leaf Node의 모든 Depth를 더했을 때 짝수인지 홀수인지에 따라 승패가 결정된다. 

Node정보를 인접 리스트로 저장한다. (방향성이 없으므로 양쪽에 모두 저장)

현재 Node의 Parent Node는 인접 리스트에서 제거한 후 dfs 탐색을 한다. 

인접 노드가 없는 경우 해당 노드는 Leaf Node이므로 현재까지 구한 depth를 count에 더한다. 

count의 짝/홀 여부를 판단하여 결과를 출력한다.

 

#소스코드

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

public class BOJ15900 {

    public static int N;
    public static HashSet<Integer>[] tree;
    public static int count = 0;
    public static void input() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new HashSet[N+1];
        for(int i = 0; i <= N ; i++) tree[i] = new HashSet<Integer>();

        StringTokenizer st = null;
        for(int i = 0; i < N-1; i++){
            st = new StringTokenizer(br.readLine());
            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());
            tree[nodeA].add(nodeB);
            tree[nodeB].add(nodeA);
        }
    }

    public static void dfs(int node, int parent, int depth){
        tree[node].remove(parent);
        if(tree[node].isEmpty()) count += depth;
        for(int adj : tree[node]){
            dfs(adj, node, depth+1);
        }
    }

    public static void main(String[] args) throws Exception{
        input();
        dfs(1, 1, 0);
        String rs = "Yes";
        if(count%2 == 0) rs = "No";
        System.out.println(rs);
    }
}