Q. 15900 자바 : 나무 탈출

Q. 15900 자바 : 나무 탈출
 
문제 : boj.kr/15900
실버 1 난이도의 문제이다.
 
성원이와 형석이가 대결을 한다.
트리 정점의 수가 주어지고, 모든 리프 노드에 게임말이 놓인다.
번갈아가며 한 번씩 말을 옮기고 옮길 수 있는 말이 없는 경우 패배하는 게임이다.
성원이가 선공을 한다면 게임판만 보고 승패 여부를 알려주는 문제이다.
 
문제는 아래와 같이 접근했다.
0. 정점의 수가 주어지므로 이를 이용해 트리를ArrayList로 구현한다.
1. 모든 리프 노드의 깊이의 합을 dfs를 사용해 구한다.
(ArrayList에 부모 노드만 가지면 == 크기가 1이면 리프 노드이다.)
2. 각자 한 번씩 움직이므로 1번값 % 2 연산을 해 결과를 구한다.
주의해야 할 점은 1번 정점의 경우 부모 노드가 없으므로 리프 노드가 아니어도 크기가 1일 수 있다는 점 이다.
 
시간 복잡도를 구하면
정점의 수 n의 최대값은 500,000이다.
모든 리프 노드에서 루트 노드(1까지 오는 최악의 경우는 약 O(n log n)이므로 시간초과는 걱정하지 않아도 된다.
자료형은 트리 구조는 배열로 표현하면 쓸데없는 메모리가 너무 많이 사용되므로 ArrayList를 사용했다.

---

풀이는 아래와 같다.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int n, cnt = 0;
    static ArrayList<Integer>[] child;

    static void input() {

        n = scan.nextInt();
        child = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) child[i] = new ArrayList<>();

        for (int i = 1; i < n; i++) {

            int v1 = scan.nextInt();
            int v2 = scan.nextInt();
            child[v1].add(v2);
            child[v2].add(v1);
        }

    }

    static void dfs(int x, int parent, int depth) {

        if (x != 1 && child[x].size() == 1) {
            cnt += depth;
            return;
        }

        for (int y: child[x]) {
            if (y == parent) continue;
            dfs(y, x, depth + 1);
        }
    }

    static void pro() {
        dfs(1, -1, 0);
        if (cnt % 2 == 0) System.out.println("No");
        else System.out.println("Yes");
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        // BufferedReader의 빠른 속도,
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}