🔗
문제 정보
※ 자세한 문제에 대한 정보의 위의 링크를 참조해주세요!
제한 사항
- 1 ≤ board 의 가로, 세로 길이 ≤ 5
- board 원소는 0 or 1
- 0 = 발판 없음, 1 = 발판 있음
- 좌측 상단 좌표 = (0, 0), 우측 상단 좌표 = (board 세로 - 1, board 가로 - 1)
- 플레이어 초기 위치는 무조건 보드 내부에 있음.
- 상대 플레이어가 있는 칸으로 이동 가능.
문제 요약
문제에서 요구한 사항을 요약하면 다음과 같습니다.
- 무조건 A부터 게임을 시작한다.
- 양 플레이어는 최적의 플레이를 한다.
- 이길 ‘수’ 있는 플레이는 최대한 빨리 승리하도록 플레이 → 최대한 적게 움직임.
- 질 ‘수밖에’ 없는 플레이어는 최대한 오래 버티도록 플레이 → 최대한 많이 움직임.
- 각 플레이어는 현재 위치에서 상하좌우로 움직인다.
- 아래 2가지 상황에서 패자와 승자가 정해진다. (게임 종료)
- 움직일 차례에 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우 → 해당 차례의 플레이어가 패배
- 같은 발판에 두 플레이어 있는 경우, 상대 플레이어가 다른 발판 이동시 남아있는 플레이어 패배.
문제 풀이
문제를 보고 아래와 같은 생각이 들었습니다.
- 격자의 크기가 작다 → 갈 수 있는 모든 경로를 다 가봐야겠다 → 완전탐색.
- 움직임 횟수를 구해야한다. → 끝까지 갔다가 돌아오면서 세야겠다. → DFS. (재귀)
근데 이 문제에서 가장 중요한 것이 ‘최적’이라는 말을 잘 해석하는 것인데 처음에는 ‘아 최대한 빨리 게임을 끝내야 하는구나’라고 이해를 해서 그렇게 코드를 짰는데 틀렸습니다. 다시 문제를 읽어보니까 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수 밖에 없는 플레이어는 최대한 오래 버티도록 플레이 해야한다라고 적혀있었고 이를 이해하지 못했습니다.
이 말이 어떤 뜻이냐면 이길 수 있다는 의미는 승리를 할 수 있는 경우의 수가 하나라도 존재한다는 의미이고 질 수 밖에 없다는 의미는 승리를 할 수 있는 경우의 수가 하나도 존재하지 않는다는 의미입니다.
이를 확인하기 위해선 어떻게 해야할까요?? 재귀를 돌면서 승리할 수 있는 경우가 존재하면 그 이후부턴 무조건 게임을 최대한 빨리 끝내려고 해야하고 승리하는 경우가 나오기 전까지는 무조건 게임을 최대한 늦게 끝내려고 해야합니다. 이를 재귀에서 상태로 관리를 해야하는데 깔끔하게 관리하기 위해선 반환값을 이용하면 됩니다.
내가 지는 경우에는 false를 반환하고 이기는 경우엔 true를 반환하는 겁니다. 근데 앞에서 움직임 횟수도 반환해야겠다고 마음 먹었으니까 반환 타입을 객체로 해서 두 정보를 모두 넘기는 방식으로 풀면 깔끔할 것 같습니다.
문제 코드
class Result {
private boolean isWin; // 승리 여부 상태 정보
private int moveCnt; // 움직임 횟수 상태 정보
public Result(boolean isWin, int moveCnt) {
this.isWin = isWin;
this.moveCnt = moveCnt;
}
public int getMoveCnt() {
return moveCnt;
}
public boolean getIsWin() {
return isWin;
}
}
class Solution {
private static final int DIR_SIZE = 4;
private int boardX, boardY;
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
public int solution(int[][] board, int[] aloc, int[] bloc) {
boardX = board.length;
boardY = board[0].length;
return move(board, aloc[0], aloc[1], bloc[0], bloc[1]).getMoveCnt(); // A부터 시작
}
private Result move(int[][] board, int ax, int ay, int bx, int by) {
if (isEnded(board, ax, ay)) {
// 이동할 수 없는 경우 -> 현재 플레이어가 지는 걸 의미, 현재 플레이어는 움직이지 않음.
// 그래서 false와 움직임 횟수 0을 반환.
return new Result(false, 0);
}
if (ax == bx && ay == by) {
// 같은 위치에 두 플레이어가 모인 경우, 현재 플레이어가 이기는 것을 의미.
// 그래서 true와 한 번 움직이면 이기는 거니까 움직임 횟수 1을 반환.
return new Result(true, 1);
}
boolean canWin = false; // 갈 수 있는 경로들 중 승리하는 경우가 하나라도 존재하는지
// 체크하기 위함.
int maxValue = -1; // 갈 수 있는 경로 중 승리하는 경우가 존재하지 않으면
// 최대한 오래 버티기
int minValue = Integer.MAX_VALUE; // 갈 수 있는 경로 중 승리하는 경우가 존재하면
// 최대한 빨리 끝내기
board[ax][ay] = 0; // 현재 위치의 발판 없애기
for (int i = 0; i < DIR_SIZE; i++) { // 상하좌우
int nx = ax + dx[i];
int ny = ay + dy[i];
if (!inRange(nx, ny) || board[nx][ny] == 0) // 다음 발판으로 갈 수 있는지 체크
continue;
Result nextResult = move(board, bx, by, nx, ny);
// A가 했으면 B, B가 했으면 A -> ax, ay, bx, by의 위치를 바꿔서 넣어줌.
if (nextResult.getIsWin()) { // 상대 플레이어가 이기면 현재 플레이어는 짐.
// 다음 갈 수 있는 모든 경로 중 승리하는 경우가 하나도 존재하지 않는 경우
// 최대한 오래 버티기 위해서 이동 횟수를 최대로 선택.
maxValue = Math.max(maxValue, nextResult.getMoveCnt());
} else { // 상대 플레이어가 지면 현재 플레이어는 이김.
// 다음 갈 수 있는 모든 경로 중 승리하는 경우가 하나라도 존재하는 경우
canWin = true; // 상태를 전달하기 위해 canWin을 true로 변경.
// 최대한 빨리 끝내기 위해서 이동 횟수를 최소로 선택.
minValue = Math.min(minValue, nextResult.getMoveCnt());
}
}
board[ax][ay] = 1; // 재귀를 빠져나가기 위해서 없앴던 발판 돌려기
// canWin이 true면 이길 수 있기에 minValue 값 이용.
// canWin이 false면 이길 수 없기에 maxValue 값 이용.
return new Result(canWin, (canWin ? minValue : maxValue) + 1);
}
private boolean isEnded(int[][] board, int x, int y) {
for (int i = 0; i < DIR_SIZE; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (inRange(nx, ny) && board[nx][ny] == 1)
return false;
}
return true;
}
private boolean inRange(int x, int y) {
return 0 <= x && x < boardX && 0 <= y && y < boardY;
}
}Uploaded by N2T