[프로그래머스] 사라지는 발판

문제 설명

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

문제 풀이

• DFS를 이용하여 풀이하였다.
• 우선 DFS 결과값은 양수, 음수로 나뉘는데 결과값 기준은 다음과 같다.

  1. 승리한 분기'가' 있으면 승리한 분기 중 가장 짧은 것을 리턴 (양수)
  2. 패배한 분기'만' 있으면 패배한 분기 중 가장 긴 것을 리턴 (음수)
  3. 이동을 할 수 없는 경우 0을 리턴

• 위 기준으로 리턴해야하기 때문에 분기 결과중 양의 최대값, 양의 최소값, 음의 최대값, 음의 최소값 4개의 값을 기준으로 결과를 리턴해야한다.
• 또한 다음 분기로 넘어갈 때 턴이 바뀌게 되므로 다음 분기값의 부호를 바꾸어 계산을 해야한다. (상대방의 최선은 나에게 최악, 상대방의 최악은 나에게 최선)
• 추가로, 위 조건에 더해서 '현재 상대가 같은 발판에 있을 경우' + '내가 움직일 수 있는 경우'를 추가로 생각해주면 된다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, M, INF = 987654321;
    public int[][] map;
    public int[] dx = {0,0,1,-1};
    public int[] dy = {1,-1,0,0};

    //turn : true -> A턴
    //turn : false -> B턴
    public int solve(int ax, int ay, int bx, int by, boolean turn) {
        int x = turn ? ax : bx;
        int y = turn ? ay : by;

        //최선의 경우 리턴
        List<Integer> list = new ArrayList<>();
        for (int d = 0; d < 4; d++) {
            int X = x + dx[d];
            int Y = y + dy[d];
            if (X < 0 || Y < 0 || X >= N || Y >= M || map[X][Y] == 0) continue;

            //현재 상대가 같은 발판에 있을 경우 (움직일 경우 바로 끝남)
            if (ax == bx && ay == by) {
                list.add(1);
                continue;
            }
            
            map[x][y] = 0;
            int res;
            if (turn) res = -solve(X, Y, bx, by, !turn);
            else res = -solve(ax, ay, X, Y, !turn);
            if (res >= 0) res++;
            else res--;
            list.add(res);
            map[x][y] = 1;
        }

        int result;
        int pMax = -INF, pMin = INF;
        int mMax = -INF, mMin = INF;
        for (int i = 0; i < list.size(); i++) {
            int num = list.get(i);
            if (num > 0) {
                pMax = Math.max(pMax, num);
                pMin = Math.min(pMin, num);
            } else {
                mMax = Math.max(mMax, num);
                mMin = Math.min(mMin, num);
            }
        }

        if (pMax == -INF && mMax == -INF) return 0;
        else if (pMax == -INF) return mMin;
        else if (pMax != -INF) return pMin;
        else return 0; //불가능 컴파일 오류 제거 
    }

    public int solution(int[][] board, int[] aloc, int[] bloc) {
        N = board.length;
        M = board[0].length;
        map = board;
        return Math.abs(solve(aloc[0], aloc[1], bloc[0], bloc[1], true));
    }
}