백준 15900. 나무 탈출 Java 풀이

문제 링크

백준 15900번: 나무 탈출

문제 요약

N개의 정점으로 이루어진 트리 모양의 게임판이 주어짐
게임 규칙:
1. 리프 노드에 게임말을 놓고 시작
2. 각 턴마다 플레이어는 게임말을 부모 노드로 이동
3. 루트 노드에 도달한 게임말은 즉시 제거
4. 더 이상 이동할 수 있는 게임말이 없는 플레이어가 패배
성원이가 먼저 시작하고, 형석이가 다음에 시작
주어진 트리 구조에서 성원이가 이길 수 있는지 판단

풀이 접근

각 리프 노드까지의 경로 길이를 계산 (움직일 수 있는 횟수)
모든 리프 노드까지의 경로 길이의 합을 구함
경로 길이의 합이 홀수이면 성원이가 이기고, 짝수이면 형석이가 이김
- 이유: 각 턴마다 한 개의 게임말이 한 칸씩 이동하며, 모든 게임말이 루트에 도달하면 게임이 종료되기 때문

구현 방법

DFS(깊이 우선 탐색)를 사용하여 트리를 탐색하면서 리프 노드까지의 경로 길이를 계산
BFS(너비 우선 탐색)로도 구현 가능

DFS를 사용하여 구현하였으며 DFS, BFS에 대한 이해는 여기를 참고

구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<Integer>[] tree;
    static boolean[] visited;
    static int totalDepth = 0;

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

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

        tree = new ArrayList[N + 1];
        visited = new boolean[N + 1];

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

        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());
            tree[a].add(b);
            tree[b].add(a);
        }

        dfs(1, 0);

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

    static void dfs(int node, int depth) {
        visited[node] = true;
        boolean isLeaf = true;

        for (int next : tree[node]) {
            if (!visited[next]) {
                isLeaf = false;
                dfs(next, depth + 1);
            }
        }

        if (isLeaf) {
            totalDepth += depth;
        }
    }
}

코드 설명

BufferedReader와 StringTokenizer를 사용해 입력을 효율적으로 처리
트리 구조를 인접 리스트로 표현
DFS를 사용해 트리를 탐색하며, 각 리프 노드까지의 깊이를 totalDepth에 누적
최종적으로 totalDepth가 홀수인지 짝수인지에 따라 결과를 출력

주요 포인트

BufferedReader는 Scanner보다 빠르므로 대용량 입력 처리에 적합
StringTokenizer는 split() 메서드보다 효율적으로 문자열을 토큰화
visited 배열로 이미 방문한 노드를 체크하여 불필요한 재탐색을 방지
리프 노드 판별: 더 이상 방문하지 않은 자식 노드가 없으면 리프 노드로 간주

이 문제는 트리 구조의 이해와 DFS 알고리즘의 응용을 요구한다.
효율적인 입력 처리와 함께 깊이 우선 탐색을 통해 문제를 해결할 수 있다.