Link | 백준 13460번 문제 : 구슬 탈출 2
📌 About
게임 보드의 크기가 최대 10 x 10이며 최대 10번의 움직임만 고려한다.
그렇기 때문에 BFS으로 충분히 해결할 수 있다.
하지만 이외의 상황 자체를 구현하는데에 시간을 소요해야 하는 문제이다.
📌 Solution
🚩 BFS 처리
먼저 BFS를 어떨게 구현해야 할지 생각해야 한다.
BFS를 구현한 Queue에는 board 정보와 몇번째 움직임인지를 전달해야 한다.
이를 State class으로 정의하는데 이때 전체 board 정보를 전달하면 메모리가 낭비된다.
메모리 낭비를 줄이기 위해 공의 위치와 움직임 횟수만 저장한다.
class State {
Point red, blue;
int time;
}공들의 시작 위치를 Queue에 우선 삽입하여 탐색을 시작한다.
만약 모두 탐색하였는데도 빨간공을 구멍에 삽입할 수 없으면 -1을 반환한다.
Queue<State> states = new LinkedList<>(Collections.singleton(initState));
while (!states.isEmpty()) {
State state = states.poll();
// state 처리
}
return -1;State 처리는 4단계의 조건문으로 처리할 수 있다.
1단계는 null 확인 작업이다.
이후의 state 처리에서 공들의 위치를 변경할 때 불가능한 상태이면 null을 queue에 삽입한다.
그렇기 때문에 null이면 이후의 작업을 하지 않는다.
파란공이 구멍에 들어간 경우가 불가능한 상태이다.
if (state == null) continue;2단계는 빨간공이 구멍에 들어간 경우이다.
이때는 정답이 되는 경우이므로 움직인 횟수를 반환한다.
if (board[state.red.x][state.red.y] == 'O') return state.time;3단계는 10번 움직인 경우를 넘기는 것이다.
10번 움직였는데도 불구하고 빨간공이 구멍에 들어가지 않았다면 이후의 작업은 무의미하다.
if (state.time == 10) continue;4단계는 게임 보드를 기울이는 단계이다.
다만 현재 공의 위치가 이전에 있었던 위치이면 이후의 작업은 무의미하다.
여기서 searched의 index는 차례대로 빨간공의 row, col 파란공의 row, col이다.
searched가 true이면 이전에 탐색한 상태이다.
if (!searched[state.red.x][state.red.y][state.blue.x][state.blue.y]) {
searched[state.red.x][state.red.y][state.blue.x][state.blue.y] = true;
// 기울이기
}🚩 보드 기울이기
보드는 4가지 방향으로 기울일 수 있다.
이를 2차원 배열로 나타내면 다음과 같다.
int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};차례대로 상, 우, 하, 좌이다. (시계방향)
각각의 기울임에 대한 결과 state를 계산한다.
if (!searched[state.red.x][state.red.y][state.blue.x][state.blue.y]) {
searched[state.red.x][state.red.y][state.blue.x][state.blue.y] = true;
for (int dir = 0; dir < 4; dir++) states.offer(tilt(state, dir));
}보드를 기울이고 나서 공들의 위치는 3개의 원소를 가지는 배열로 저장한다.
move 함수는 이후에 설명한다.
int[] red = move(state.red, direction);
int[] blue = move(state.blue, direction);각각의 배열은 {공의 row, 공의 col, 공의 움직인 칸의 수}를 의미한다.
만약 파란공이 구멍에 들어갔다면 null을 반환한다.
if (board[blue[0]][blue[1]] == 'O') return null;참고로 move함수는 각각의 공이 독립적으로 움직인다.
그렇기 때문에 결과적으로 공이 동일한 곳에 위치할 수 있다.
만약 두 공이 같은 위치에 있다면 둘 중 하나는 움직인 반대 방향으로 한 칸 이동해야 한다.
예를 들어 빨간공이 [2, 3]에 있고 파란공이 [5, 3]에 있으며 구멍과 장애물은 고려하지 말아보자.
게임 보드를 위로 기울이면 빨간공과 파란공은 둘 다 [1, 3]에 위치할 것이다. ([0, 3]은 벽이다.)
하지만 두 공은 사실 독립적이지 않으니 파란공은 [2, 3]에 위치해야 한다.
때문에 파란공을 위의 반대 방향인 아래 방향으로 1 옮겨서 [2, 3]으로 변경한다.
이 때 3번째 값인 공의 움진인 칸 수를 사용한다.
더 많이 움직인 공이 뒤에 있던 공이기 때문에 해당 공을 뒤로 한 칸 옮긴다.
else if (red[0] == blue[0] && red[1] == blue[1]) {
if (red[2] > blue[2]) {
red[0] -= moves[direction][0];
red[1] -= moves[direction][1];
} else {
blue[0] -= moves[direction][0];
blue[1] -= moves[direction][1];
}
}마지막에 새로운 상태를 생성하여 반화한다.
return new State(new Point(red[0], red[1]), new Point(blue[0], blue[1]), state.time + 1);🚩 공 움직이기
공을 움직일 때 고려해야 하는 것은 구멍과 벽이다.
구멍이나 벽을 만나면 더는 움직이지 않는다.
이때 차이점은 구멍은 구멍에서 멈추고 벽은 벽 이전에서 멈춘다는 것이다.
공을 우선 움직이고 나서 이를 판단하기 때문에 벽일 때는 한 칸 뒤로 옮긴다.
private int[] move(Point ball, int direction) {
int row = ball.x;
int col = ball.y;
int count = 0;
while (true) {
row += moves[direction][0];
col += moves[direction][1];
count++;
if (board[row][col] == 'O') break;
else if (board[row][col] == '#') {
row -= moves[direction][0];
col -= moves[direction][1];
count--;
break;
}
}
return new int[]{row, col, count};
}📌 Code
State
class State {
Point red, blue;
int time;
public State() {
}
public State(Point red, Point blue, int time) {
this.red = red;
this.blue = blue;
this.time = time;
}
}private final int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private char[][] board;
private boolean[][][][] searched;
public void solve() throws IOException {
result.append(search(input()));
}
private int search(State initState) {
Queue<State> states = new LinkedList<>(Collections.singleton(initState));
while (!states.isEmpty()) {
State state = states.poll();
if (state == null) continue;
if (board[state.red.x][state.red.y] == 'O') return state.time;
if (state.time == 10) continue;
if (!searched[state.red.x][state.red.y][state.blue.x][state.blue.y]) {
searched[state.red.x][state.red.y][state.blue.x][state.blue.y] = true;
for (int dir = 0; dir < 4; dir++) states.offer(tilt(state, dir));
}
}
return -1;
}
private State tilt(State state, int direction) {
int[] red = move(state.red, direction);
int[] blue = move(state.blue, direction);
if (board[blue[0]][blue[1]] == 'O') return null;
else if (red[0] == blue[0] && red[1] == blue[1]) {
if (red[2] > blue[2]) {
red[0] -= moves[direction][0];
red[1] -= moves[direction][1];
} else {
blue[0] -= moves[direction][0];
blue[1] -= moves[direction][1];
}
}
return new State(new Point(red[0], red[1]), new Point(blue[0], blue[1]), state.time + 1);
}
private int[] move(Point ball, int direction) {
int row = ball.x, col = ball.y, count = 0;
while (true) {
row += moves[direction][0];
col += moves[direction][1];
count++;
if (board[row][col] == 'O') break;
else if (board[row][col] == '#') {
row -= moves[direction][0];
col -= moves[direction][1];
count--;
break;
}
}
return new int[]{row, col, count};
}
private State input() throws IOException {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int ROW = Integer.parseInt(tokenizer.nextToken());
int COL = Integer.parseInt(tokenizer.nextToken());
board = new char[ROW][COL];
searched = new boolean[ROW][COL][ROW][COL];
State state = new State();
for (int row = 0; row < ROW; row++) {
String rowLine = reader.readLine();
for (int col = 0; col < COL; col++) {
board[row][col] = rowLine.charAt(col);
if (board[row][col] == 'R') {
state.red = new Point(row, col);
board[row][col] = '.';
} else if (board[row][col] == 'B') {
state.blue = new Point(row, col);
board[row][col] = '.';
}
}
}
return state;
}