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

문제

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

풀이

처음 접해보는 유형의 문제였다. 2차원 배열의 map을 양쪽 사람이 하나씩 점령해나가는 형태는 많이 만나왔다. 각각 BFS를 돌리며 다른 한쪽을 침범하지 않도록 하는 문제들이었는데 이 문제는 조금 다르다.

1. 이길 수 있는 방식이 있는지 찾아야한다.
2. 이길 수 있다면 최소한의 움직임으로 이겨야 한다.
3. 이길 수 없다면 최대한 피해다녀야 한다.

이 문제를 해결해나가는 과정
1. 발판의 최대 개수가 크지 않기 때문에 DFS를 이용하여 번갈아가며 진행
2. A부터 진행하는 것으로 가정
3. 누군가는 무조건 이기고 누군가는 무조건 지게되는 상황이 주어진다. 따라서 A를 기준으로 이긴다면 가장 최소한의 횟수, 진다면 최대 횟수를 반환하도록 설정한다.
4. 문제 조건상 발판에서 빠져나갈 때 0으로 바뀌도록 설정한다.(이를 확인하는 과정도 필요)

자세한 풀이

https://developer-ellen.tistory.com/168

코드

class Solution {
    static int N, M;

    static int[][] map;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    public int solution(int[][] board, int[] aloc, int[] bloc) {
        int answer = -1;

        N = board.length;
        M = board[0].length;

        map = board;

        Result result = DFS(aloc[0], aloc[1], bloc[0], bloc[1], 0, 0);
        answer = result.count;
        return answer;
    }

    static Result DFS(int Ax, int Ay, int Bx, int By, int moveA, int moveB) {

        boolean win = false;
        int winCnt = 5 * 5;
        int loseCnt = moveA + moveB;

        if (moveA == moveB && map[Ax][Ay] == 1) { //같은 곳에 위치했을 때 떨어지게 되는지 확인
            for (int i = 0; i < 4; i++) {
                int nx = Ax + dx[i];
                int ny = Ay + dy[i];
                if (checkRange(nx, ny)) {
                    map[Ax][Ay] = 0;
                    Result result = DFS(nx, ny, Bx, By, moveA + 1, moveB); // 상대방 진행
                    win |= !result.win; // 상대방이 false를 반환했다면 나는 true, 4번의 횟수 중에서 한 번이라도 이길 수 있다면 그걸 가져간다
                    if (result.win) { // 상대방이 이겼다면
                        loseCnt = Math.max(result.count, loseCnt);
                    } else {
                        winCnt = Math.min(result.count, winCnt);
                    }
                    map[Ax][Ay] = 1;
                }
            }
        } else if (moveA > moveB && map[Bx][By] == 1) {
            for (int i = 0; i < 4; i++) {
                int nx = Bx + dx[i];
                int ny = By + dy[i];
                if (checkRange(nx, ny)) {
                    map[Bx][By] = 0;
                    Result result = DFS(Ax, Ay, nx, ny, moveA, moveB + 1); // 상대방 진행
                    win |= !result.win; // 상대방이 false를 반환했다면 나는 true, 4번의 횟수 중에서 한 번이라도 이길 수 있다면 그걸 가져간다
                    if (result.win) { // 상대방이 이겼다면
                        loseCnt = Math.max(result.count, loseCnt);
                    } else {
                        winCnt = Math.min(result.count, winCnt);
                    }
                    map[Bx][By] = 1;
                }
            }
        }

        return new Result(win, win ? winCnt : loseCnt);
    }

    static boolean checkRange(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 0) return false;
        return true;
    }

    static boolean checkVisitable(int x, int y) {
        if (map[x][y] == 0) return false;
        return true;
    }

    static class Result {
        boolean win;
        int count;

        public Result(boolean win, int count) {
            this.win = win;
            this.count = count;
        }
    }
}