[BOJ 15900] 나무 탈출 (Java, DFS, Tree)

 

 

---

문제 링크

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

15900번: 나무 탈출

---

문제 풀이

- 노드 N (1 ~ 500,000) 이때 1번 노드가 정점 노드로 주어짐

- 간선의 수 N - 1 

- LEAF 노드의 DEPTH를 구하고 그 합이 홀수인 경우 Yes, 짝수인 경우 No로 답을 구하면 됨

- 시간복잡도 : O(V + E) = O(500,000 + 499,999) 

 

DEPTH 배열을 따로 구할 필요 없이 전역 변수에 LEAF 노드의 깊이(depth)를 다 합산한 후 결과 구해도 됨

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {

    static int N, ANS;
    
    static List<Integer>[] tree;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        tree = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) tree[i] = new ArrayList();

        for(int i = 1; i <= (N - 1); i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            tree[from].add(to);
            tree[to].add(from);
        }

        br.close();
    }

    static void dfs(int node, int parent, int depth) {
        if(node != 1 && tree[node].size() == 1 && tree[node].get(0) == parent) {
            ANS += depth;
            return;
        }

        for(int child : tree[node]) {
            if(child == parent) continue;

            dfs(child, node, depth + 1);
        }
    }

    static void pro() {
        dfs(1, -1,  0);

        System.out.println(ANS % 2 == 1 ? "Yes" : "No");
    }

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

}