Programmers - 사라지는 발판(Java)

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

코딩테스트 연습 - 사라지는 발판

 

풀이

다음 2가지의 경우에 승패가 결정됨

1. 상하좌우 4방향 중 어떠한 방향으로도 이동 불가인 경우
2. 하나의 발판에 2명이 위치할 때, 한명이 다른 발판으로 이동하여 현재 발판이 사라질 때 

지는 플레이어든 이기는 플레이어든 각자 최적의 플레이로 진행

• 이기는 플레이어 - 최대한 빨리 승리하는 방향으로 진행 -> 움직이는 횟수를 최소화
• 지는 플레이어 - 최대한 오래 버티는 방향으로 진행 -> 움직이는 횟수를 최대화

---

전역 변수 및 클래스

static int[] dy = {1, 0, -1, 0};
static int[] dx = {0, 1, 0, -1};
static int N, M;
static int MAX = 987654321;

static class turn {
	boolean isWin;
	int cnt;

	turn(boolean isWin, int cnt) {
		this.cnt = cnt;
		this.isWin = isWin;
	}
}

 

dfs 함수

재귀함수로 각 플레이어 차례마다 함수 실행하며 2가지의 승패가 결정되는 경우를 확인 

 

현재 순번을 기준으로 위치 확인 및 승패 확인

현재 순번의 플레이어 위치에 발판이 없다면 졌다고 판단(승패결정 조건 2번)

 

 

현재 순번을 기준으로 상하좌우 4가지 방향이동 후 다음 순번에게 dfs 함수를 재귀 실행

dfs(board, aloc, bloc, !isATurn, cnt+1)  ----> isATurn을 반전시켜서 True, false, True, false, ....로 번갈아 실행

 

이후 함수의 실행 결과 turn의 isWin에 따라 진행

isWin == True : 다음 순번이 이겼으므로 현재 순번은 졌다는 의미

• lose = MAX(turn.cnt, lose) ---> 현재 순번이 졌으므로 가장 많이 이동하는 방향으로 진행

isWin == False : 다음 순번이 졌으므로 현재 순번은 이겼다는 의미

• win = MIN(turn.cnt, win) --->현재 순번이 이겼으므로 가장 적게 이동하는 방향으로 진행

 

현재 순번기준 4가지 방향 탐색 후 상황에 맞게끔 return

1. 4가지 방향 모두 이동할 수 없는 경우(승패 결정조건 1번)
   • 현재 순번이 졌으므로 new turn(false, cnt)를 return
2. win != MAX(987654321)
   • 4가지 방향으로 진행한 결과중 이긴 결과가 하나라도 존재 -> 현재 순번 승리
   • 현재 순번이 이겼으므로 new turn(true, win)를 return
3. win == MAX(987654321)
   • 4가지 방향으로 진행한 결과중 이긴 결과가 X -> 현재 순번 패배
   • 현재 순번이 졌으므로 new turn(false, lose)를 return

 

private static turn dfs(int[][] board, int[] aloc, int[] bloc, boolean isATurn, int cnt) {
	int ay = aloc[0];
	int ax = aloc[1];
	int by = bloc[0];
	int bx = bloc[1];
	
	// 승패 결정조건 2번
	if ((board[ay][ax] == 0 && isATurn) || (board[by][bx] == 0 && !isATurn))
		return new turn(false, cnt);

	int win = MAX;
	int lose = 0;
	int y, x;
	if (isATurn) {
		y = ay;
		x = ax;
	} else {
		y = by;
		x = bx;
	}
	board[y][x] = 0;

	turn res = null;
	boolean canGo = false;
	for (int d = 0; d < 4; d++) {
		int ny = y + dy[d];
		int nx = x + dx[d];

		if ((ny < 0 || nx < 0 || ny >= N || nx >= M) || board[ny][nx] == 0) continue;
		canGo = true;
		
		if (isATurn) {
			res = dfs(board, new int[]{ny, nx}, bloc, !isATurn, cnt + 1);
		} else {
			res = dfs(board, aloc, new int[]{ny, nx}, !isATurn, cnt + 1);
		}

		// 다음 순번이 이길 경우 현재 순번이 패배 -> 최대의 움직임
		if (res.isWin) {
			lose = Math.max(lose, res.cnt);
		}
		// 다음 순번이 질 경우 현재 순번이 승리 -> 최소의 움직임
		else {
			win = Math.min(win, res.cnt);
		}
	}
	board[y][x] = 1;
    
	if (!canGo) {// 승패 결정조건 1번
		return new turn(false, cnt);
	} else if (win != MAX) {
		return new turn(true, win);
	} else {
		return new turn(false, lose);
	}
}

---

전체 코드

import java.io.*;

class Solution {
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int N, M;
    static int MAX = 987654321;

    static class turn {
        boolean isWin;
        int cnt;

        turn(boolean isWin, int cnt) {
            this.cnt = cnt;
            this.isWin = isWin;
        }
    }

    public static int solution(int[][] board, int[] aloc, int[] bloc) {
        N = board.length;
        M = board[0].length;

        turn res = dfs(board, aloc, bloc, true, 0);

        return res.cnt;
    }

    private static turn dfs(int[][] board, int[] aloc, int[] bloc, boolean isATurn, int cnt) {
        int ay = aloc[0];
        int ax = aloc[1];
        int by = bloc[0];
        int bx = bloc[1];

        if ((board[ay][ax] == 0 && isATurn) || (board[by][bx] == 0 && !isATurn))
            return new turn(false, cnt);

        int win = MAX;
        int lose = 0;
        int y, x;
        if (isATurn) {
            y = ay;
            x = ax;
        } else {
            y = by;
            x = bx;
        }
        board[y][x] = 0;

        turn res = null;
        boolean canGo = false;
        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];

            if ((ny < 0 || nx < 0 || ny >= N || nx >= M) || board[ny][nx] == 0) continue;
            canGo = true;
            if (isATurn) {
                res = dfs(board, new int[]{ny, nx}, bloc, !isATurn, cnt + 1);
            } else {
                res = dfs(board, aloc, new int[]{ny, nx}, !isATurn, cnt + 1);
            }

            // 다음 순번이 이길 경우 현재 순번이 패배 -> 최대의 움직임
            if (res.isWin) {
                lose = Math.max(lose, res.cnt);
            }
            // 다음 순번이 질 경우 현재 순번이 승리 -> 최소의 움직임
            else {
                win = Math.min(win, res.cnt);
            }
        }

        board[y][x] = 1;
        // 어떠한 방향으로도 이동 불가
        if (!canGo) {
            return new turn(false, cnt);
        } 
        // 현재 순번이 이기는 경우
        else if (win != MAX) {
            return new turn(true, win);
        } 
        // 현재 순번이 지는 경우
        else {
            return new turn(false, lose);
        }
    }

}