문제 정의
- 빨간 수레와 파란 수레가 주어짐
- 퍼즐판 내에 각각의 시작 지점과 도착 지점, 그리고 벽이 주어짐
- 이 퍼즐을 푸는데 필요한 턴의 최솟값 구하기
제약 조건
- 수레는 벽이나 격자 판 밖으로 움직일 수 없음
- 수레는 자신이 방문했던 칸으로 움직일 수 없음
- 자신의 도착 칸에 위치한 수레는 움직이지 않음
- 동시에 두 수레를 같은 칸으로 움직일 수 없음
- 수레끼리 자리를 바꾸며 움직일 수 없음
접근 방법
DFS? BFS?
저는 처음에 두 개의 공을 활옹해 문제를 해결하는 것이기 때문에
백준에 있는 구슬 탈출 시리즈 문제를 생각해서 BFS로 문제를 해결하면 될 줄 알았습니다.
BFS로 풀면 해결할 수 없다.
왜 구슬 탈출은 BFS로 해결 가능하고
왜 이 문제는 BFS로 해결이 불가능할까요?
그 이유는 이동 방식에 있습니다.
구슬 탈출: 두 구슬이 같은 방향으로만 이동함
수레 움직이기: 두 구슬이 서로 다른 방향으로 이동 가능함
따라서 구슬 탈출은 두 구슬을 하나의 visited 배열을 통해 문제를 해결할 수 있지만
해당 문제는 서로가 다른 이동을 하고 각각이 이동한 곳은 다시 갈 수 없다는 조건이 있기 때문입니다.
또한 이동 방향에 대한 제약이 없기 때문에
visited 배열을 수레 별로 분리해서 처리해야 합니다.
제약 조건 처리
이후 문제는 다른 DFS 문제와 같지만 제약 조건이 조금 까다롭습니다.
제약 조건은 다음과 같습니다.
1. 수레는 벽이나 격자 판 밖으로 움직일 수 없음
2. 수레는 자신이 방문했던 칸으로 움직일 수 없음
3. 자신의 도착 칸에 위치한 수레는 움직이지 않음
4. 동시에 두 수레를 같은 칸으로 움직일 수 없음
5. 수레끼리 자리를 바꾸며 움직일 수 없음
// 4번 제약 조건
if (nry == nby && nrx == nbx) continue;
// 5번 제약 조건
if (nry == by && nrx == bx && nby == ry && nbx == rx) continue;
// 1번 제약 조건
if (!inbound(nry, nrx, nby, nbx) || isWall(nry, nrx, nby, nbx)) continue;
// 2번 제약 조건
if ((!rFlag && rVisited[nry][nrx]) || (!bFlag && bVisited[nby][nbx])) continue;이런 제약 조건에 대해서만 처리 해주고
3번 제약 조건인 현재 도착지점에 들어왔는지 여부에 따른 응용 처리만 해준다면
일반적인 DFS로 문제를 해결할 수 있습니다.
도착 지점에 도착한 수레에 따른 처리
둘 다 도착 지점에 들어오면 턴의 최솟값 갱신과 리턴을 해주면 되지만
둘 중 하나의 수레만 도착 지점에 도착한 경우
도착한 수레에 대한 처리가 필요합니다.
다음 두 수레의 좌표에 대한 처리
int nry = ry + (rFlag ? 0 : dy[rd]);
int nrx = rx + (rFlag ? 0 : dx[rd]);
int nby = by + (bFlag ? 0 : dy[bd]);
int nbx = bx + (bFlag ? 0 : dx[bd]);이미 도착한 수레의 경우 이동할 필요가 없습니다.
이에 대한 처리를 해주어야 합니다.
어떤 수레가 도착했는지 파악
boolean rFlag = rVisited[ery][erx];
boolean bFlag = bVisited[eby][ebx];이 값이 true가 되는 수레가 도착한 수레입니다.
도착한 수레는 이동하지 않도록 해야합니다.
if ((!rFlag && rVisited[nry][nrx]) || (!bFlag && bVisited[nby][nbx])) continue;이전 제약 조건에서 "수레는 자신이 방문했던 칸으로 움직일 수 없음" 조건입니다.
현재 도착해서 플래그가 true인 경우에 대해서는 방문 체크를 하면 안됩니다.
아직 방문되지 않았고 이번에 방문되는 경우에만 체킹하도록 조건을 작성했습니다.
아직 도착하지 않은 경우에 대해서 이동에 대한 백트래킹 처리
if (!rFlag) rVisited[nry][nrx] = true;
if (!bFlag) bVisited[nby][nbx] = true;
dfs(nry, nrx, nby, nbx, turn + 1);
if (!rFlag) rVisited[nry][nrx] = false;
if (!bFlag) bVisited[nby][nbx] = false;플래그가 켜진 상황에도 백트래킹을 하게 된다면
DFS를 수행하고 돌아온 후에 이미 도착한 상황인데도
false로 전환되면서 로직이 깨지게 되기 때문에
이미 도착한 경우에는 방문처리를 제외합니다.
이렇게 정리하면 해당 문제를 해결할 수 있습니다.
코드
import java.util.*;
class Solution {
static final int MAX = 1000000;
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, -1, 0, 1};
static boolean[][] rVisited;
static boolean[][] bVisited;
static int[][] board;
static int sry, srx, sby, sbx;
static int ery, erx, eby, ebx;
static int answer;
static int N, M;
public int solution(int[][] maze) {
init(maze);
dfs(sry, srx, sby, sbx, 0);
return answer == MAX ? 0 : answer;
}
static void dfs(int ry, int rx, int by, int bx, int turn) {
if (turn >= answer) return;
boolean rFlag = rVisited[ery][erx];
boolean bFlag = bVisited[eby][ebx];
if (rFlag && bFlag) {
answer = Math.min(answer, turn);
return;
}
for (int rd = 0; rd < 4; rd++) {
for (int bd = 0; bd < 4; bd++) {
int nry = ry + (rFlag ? 0 : dy[rd]);
int nrx = rx + (rFlag ? 0 : dx[rd]);
int nby = by + (bFlag ? 0 : dy[bd]);
int nbx = bx + (bFlag ? 0 : dx[bd]);
if (nry == nby && nrx == nbx) continue;
if (nry == by && nrx == bx && nby == ry && nbx == rx) continue;
if (!inbound(nry, nrx, nby, nbx) || isWall(nry, nrx, nby, nbx)) continue;
if ((!rFlag && rVisited[nry][nrx]) || (!bFlag && bVisited[nby][nbx])) continue;
if (!rFlag) rVisited[nry][nrx] = true;
if (!bFlag) bVisited[nby][nbx] = true;
dfs(nry, nrx, nby, nbx, turn + 1);
if (!rFlag) rVisited[nry][nrx] = false;
if (!bFlag) bVisited[nby][nbx] = false;
}
}
}
static boolean isWall(int ry, int rx, int by, int bx) {
return board[ry][rx] == 5 || board[by][bx] == 5;
}
static boolean inbound(int ry, int rx, int by, int bx) {
return 0 <= ry && ry < N && 0 <= rx && rx < M && 0 <= by && by < N && 0 <= bx && bx < M;
}
static void init(int[][] maze) {
N = maze.length;
M = maze[0].length;
answer = MAX;
board = maze;
rVisited = new boolean[N][M];
bVisited = new boolean[N][M];
rVisited[sry][srx] = true;
bVisited[sby][sbx] = true;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] == 1) {
sry = i;
srx = j;
}
else if (board[i][j] == 2) {
sby = i;
sbx = j;
}
else if (board[i][j] == 3) {
ery = i;
erx = j;
}
else if (board[i][j] == 4) {
eby = i;
ebx = j;
}
}
}
}
}