[백준] 15900번 : 나무 탈출

15900번: 나무 탈출

---

[DFS]

몇 시간을 고민해보아도 풀지 못해 풀이를 찾아 보던 중, 너무 간단하게 푼 풀이가 있어 많은 것을 깨달았다. 나는 아직 DFS 응용을 하기에는 벅차다는 것을.. 문제의 실마리를 찾을 때 조금 더 집중하고 깊이 들여다보는 습관을 길러야겠다.

 

다음 풀이는 Sleeping Rabbit님의 블로그를 참고하였다.

리프노드의 높이를 구하고, 각 리프노드들의 높이를 모두 더한 합이 짝수이면 실패, 홀수이면 성공 이라는 간단한 명제로 풀이를 진행하셨는데, 내가 너무 어렵게 생각해오던 것이 너무 허탈했다.

 

내가 고심끝에 접근한 것은 DFS의 시작 점이 리프노드가 아닌 루트 노드라는 것..

# Code </>

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 = new ArrayList[500001];
    static boolean[] visit = new boolean[500001];
    static int heightSum = 0;

    static void DFS(int x, int height){

        visit[x] = true;
        boolean isLeaf = true;

        for(int next : list[x])
            if(!visit[next]) {
                isLeaf = false;
                DFS(next, height + 1);
            }

        if(isLeaf)
            heightSum += height;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

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

        for(int i=1; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            list[v1].add(v2);
            list[v2].add(v1);
        }
        DFS(1, 0);
        System.out.println(heightSum % 2 != 0? "Yes":"No");
    }
}

 

# Reference

Sleeping Rabbit님의 블로그