2022 카카오 블라인드 사라지는 발판

https://school.programmers.co.kr/learn/courses/30/lessons/92345

1. 이 문제의 핵심 board의 가로 세로길이가 5이다.
   -> 완전 탐색으로 풀 수 있다.
2. 이길 수 있는 플레이어는 무조건 최적으로 움직여 게임을 빨리 끝내야한다. (Min)
3. 질 수 있는 플레이어는 무조건 도망다녀 최고로 많이 움직여야한다.(Max)
4. 모든 경우의 수를 다 탐색해서 백 트래킹 한다.

• 다음 턴에서 상대가 이겼을 때 -> 지금의 턴이 진다.
  (Max 값을 갱신해준다)
• 다음 턴에서 상대가 졌을 때 -> 지금의 턴이 이긴다.
  (Min 값을 갱신해준다)

5. 백트래킹을 빠져나오면서 board를 다시 되돌리면서 기록을 return해서 갱신해간다.

   import java.util.*;
   class Solution {
      static int dx[] = {-1, 1, 0, 0};
      static int dy[] = {0, 0, -1, 1};
      static int row;
      static int col;
      static int max;
      public int solution(int[][] board, int[] aloc, int[] bloc) {
          int answer = -1;
          row = board.length;
          col = board[0].length;
          
          
         // A부터 시작 값 false
          boolean start = false;
          max = Integer.MAX_VALUE;
          
          Node nd = DFS(aloc[0], aloc[1], bloc[0], bloc[1], start, board, 0);
          
          
          
          return nd.cnt;
      }
      static Node DFS(int ax, int ay ,int bx, int by, boolean turn, int[][] board, int time) {
          // 내턴인데 내 바닥이 0 일때 승부는 정해졌다
          if((board[ax][ay] == 0 && !turn) || (board[bx][by] == 0 && turn)) {
              return new Node(time, false);
          }
          
          int win = max;
          int lose = 0;
          int x, y;
          if(!turn) {
              x = ax;
              y = ay;
          } else {
              x = bx;
              y = by;
          }
        
          board[x][y] = 0;
          Node res = null;
          boolean canGo = false;
          for(int i = 0; i < 4; i++) {
              int nx = x + dx[i];
              int ny = y + dy[i];
              
              if(nx < 0 || ny < 0 || nx >= row || ny >= col || board[nx][ny] == 0) {
                  continue;
              }
              canGo = true;
              if(!turn) {
                  // Aturn인 경우
                  res = DFS(nx, ny, bx, by, !turn, board, time + 1);
              } else {
                  res = DFS(ax, ay, nx, ny, !turn, board, time + 1);
              }
              
              if(res.isWin) {
                  // 다음번 순번이 이김
                  lose = Math.max(lose, res.cnt);
              } else {
                  // 현재가 이김
                  win = Math.min(win, res.cnt);
              }
              
          }
          board[x][y] = 1;
          if(!canGo) {
              return new Node(time, false);
          } else if(win != max) {
              // 현재 순번이 이김
              return new Node(win , true);
          } else {
              // 현재 순번이 짐
              return new Node(lose, false);
          }
          
      }
      
      
      
     static class Node {
         int cnt;
         boolean isWin;
         
         public Node(int cnt, boolean isWin){
             this.cnt = cnt;
             this.isWin = isWin;
         }
         
     }
   }