About
- 사이트: 프로그래머스
- 이름: 사라지는 발판
- 수준: 3
- 유형: DFS
- 출제: 2022 KAKAO BLIND RECRUITMENT
- 주소: https://programmers.co.kr/learn/courses/30/lessons/92345
해설
- 최대 사이즈가 크지 않다 (1 <= 가로&세로 길이 <= 5)
- 움직일 때마다 밟고 있던 발판이 사라진다
라는 조건 덕분에 완전탐색으로 풀어도 문제가 없다.
DFS로 풀도록 하는데, 다음 조건으로 return 해본다.
- 이길 수 있는 케이스가 있다면 그 중에서 최선으로 이기는 케이스를 리턴한다. (승리)
- 질 수 밖에 없다면 최대한 오래 버티는 케이스를 리턴한다. (패배)
board[ax][ay] 를 0으로, B의 턴을 실행하고 나서 결과를 반환받으면 1로 만들어줌으로써 다른 분기를 검사할 수 있도록 한다.
승자는 가장 빨리 이기는 걸 선택하고, 패자는 최대한 늦게 지는 걸 선택한다.
모두 이기는 경우 최대한 빨리 이기는 것을, 모두 지는 경우 최대한 늦게 지는 걸 선택한다.
코드
public class Q92345 {
int[][] board;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int MAX_X;
int MAX_Y;
public int solution(int[][] board, int[] aloc, int[] bloc) {
this.board = board;
MAX_X = board.length;
MAX_Y = board[0].length;
return dfs(aloc[0], aloc[1], bloc[0], bloc[1]);
}
int dfs(int ax, int ay, int bx, int by) {
if (board[ax][ay] == 0) {
return 0;
}
int result = 0;
for (int[] dir : dirs) {
int nx = ax + dir[0];
int ny = ay + dir[1];
if (isOut(nx, ny) || board[nx][ny] == 0) {
continue;
}
board[ax][ay] = 0;
int bMove = dfs(bx, by, nx, ny) + 1;
board[ax][ay] = 1;
if (result % 2 == 0 && bMove % 2 == 1) {
result = bMove;
} else if (result % 2 == 0 && bMove % 2 == 0) {
result = Math.max(result, bMove);
} else if (result % 2 == 1 && bMove % 2 == 1) {
result = Math.min(result, bMove);
}
}
return result;
}
boolean isOut(int x, int y) {
return x < 0 || x >= MAX_X || y < 0 || y >= MAX_Y;
}
}