[엘리스 알고리즘 코드 챌린지] Day 4. 트리 위의 게임 (Java)

문제

---

핵심

• 두 플레이어는 항상 최선의 선택을 한다고 하였다.
• 내부 노드는 후공이 최대한 낮은 점수를 받도록 다음 노드를 선택해야한다.
• 리프 노드에서는 선공이 항상 승리한다. (공격하고 바로 끝나기 때문에)

내부 노드에서 시작하는 경우는 최종 결과가 자식 노드의 결과와 연관되어 있다.

그리고 리프 노드에서 시작하는 경우는 확정적이기 때문에 리프 노드에서 시작하는 경우를 기반으로 루트에서 시작하는 경우까지 점차 확장해가면 해결할 수 있다.

---

구현

1번 예제의 트리 모양은 아래와 같다. 

  1
 /|\
2 3 5
 /
4

 

이를 기반으로 구현을 한다면

 

DP 테이블 

정의

D[i] : i번 노드에서 시작했을 때, 선공과 후공의 점수차 (둘 다 최선의 선택을 한 경우)

 

초기값 (리프 노드에서 시작하면 선공으로 점수를 얻고 바로 종료된다)

D[2] = 2

D[4] = 4

D[5] = 5

 

점화식

D[i] = i - (모든 자식 노드 번호 j에 대한 D[j] 중 가장 작은 값)

 

리프 노드부터 탐색하기

BFS를 이용해서 1번 노드부터 탐색하면, 루트부터 리프까지 차례대로 탐색하게 된다.
이를 모두 스택에 넣으면 반대로 리프노드부터 높이의 역순으로 추출할 수 있다.

 

진행

이제 번호를 추출하면서 로직을 수행한다.

•    리프 노드라면 자기 노드 번호가 D 배열의 초기값을 설정한다.
•    내부 노드라면 점화식을 통해 D 배열의 값을 구한다.

---

Code (Java)

import java.util.*;

public class Main {
    static List<Integer>[] adjList;
    static int[] dp;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        adjList = new ArrayList[n + 1];
        dp = new int[n + 1];
        visited = new boolean[n + 1];

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

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adjList[u].add(v);
            adjList[v].add(u);
        }

        // BFS를 통해 정점을 스택에 저장
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            stack.push(node);
            for (int child : adjList[node]) {
                if (!visited[child]) {
                    visited[child] = true;
                    queue.add(child);
                }
            }
        }

        // 스택을 이용해 DP 값을 계산
        Arrays.fill(visited, false);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            visited[node] = true;
            boolean isLeaf = true;

            int minChildValue = Integer.MAX_VALUE;
            for (int child : adjList[node]) {
                if (visited[child]) {
                    isLeaf = false;
                    minChildValue = Math.min(minChildValue, dp[child]);
                }
            }

            if (isLeaf) {
                dp[node] = node; // 리프 노드의 초기값
            } else {
                dp[node] = node - minChildValue;
            }
        }

        // 결과를 출력
        for (int i = 1; i <= n; i++) {
            if (dp[i] >= 0) {
                System.out.println(1);  // 선공 승리
            } else {
                System.out.println(0);  // 후공 승리
            }
        }

        sc.close();
    }
}