백준 13460 - 구슬 탈출2
Updated:
Java
13460 번 - 구슬 탈출2
문제
구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M
왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작으로 구슬을 빼내야 한다.
빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다.
접근 방법
- 상하좌우 기울이는 방법을 10번 세팅한다. 이는 4^10 == 1,048,576
- 구슬을 이동시킨다.
- 만약 상/하 일때 B,R이 같은 x축에 있으면, y값 비교하여 둘 중 어느 공을 먼저 이동할지 정한다, 좌/우 일대 B,R이 같은 y축에 있으면 x값 비교
- 구멍을 만나면 종료하고, 몇번 방문했는지 기록한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, result = Integer.MAX_VALUE;
static char[][] board;
static int[] dir;
static int Ry, Rx, By, Bx;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
n = stoi(stk.nextToken());
m = stoi(stk.nextToken());
board = new char[n][m];
dir = new int[10];
for(int i = 0; i < n; i++) {
String str = br.readLine();
for(int j = 0; j < m; j++) {
board[i][j] = str.charAt(j);
if(board[i][j] == 'B') {
By = i;
Bx = j;
}
else if(board[i][j] == 'R') {
Ry = i;
Rx = j;
}
}
}
DFS(0);
if(result == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(result);
br.close();
}
// 총 10번의 어떻게 기울일 것인가 DFS로 모두 확인한다.
static void DFS(int lv) {
if(lv == 10) {
char[][] nBoard = new char[n][m];
for(int i = 0; i < n; i++) {
nBoard[i] = board[i].clone();
}
int rst = Move(nBoard);
if(rst != -1) {
result = Math.min(result, rst);
}
return;
}
for(int i = 0; i < 4; i++) {
dir[lv] = i;
DFS(lv+1);
}
}
// 우 하 좌 상
static int[] dy = {0, 1, 0, -1};
static int[] dx = {1, 0, -1, 0};
static int Move(char[][] mBoard) {
int curD;
int by = By, bx = Bx, ry = Ry, rx = Rx;
int y,x; // 처음 공 위치
boolean bH = false, rH = false;
boolean isRedFirst = true;
// 10번 각 방향으로 기우린다.
for(int i = 0; i < 10; i++) {
curD = dir[i]; // 상 우 하 좌로 기운다.
// 상, 하로 이동하며 R,B가 같은 위치 x에 있으면
if((curD == 1 || curD == 3) && bx == rx) {
// 위로 올라가는 경우
if(curD == 3) {
if(ry < by) // 빨간 공이 더 위에 있을 시
isRedFirst = true;
else
isRedFirst = false;
}
// 아래로 내려가는 경우
else {
if(ry > by) // 빨간 공이 더 아래에 있을 때
isRedFirst = true;
else
isRedFirst = false;
}
}
// 좌, 우로 이동하며 R,B가 같은 위치 y에 있으면
else if((curD == 0 || curD == 2) && by == ry) {
// 우로 이동하는 경우
if(curD == 0) {
if(rx > bx) // 빨간 공이 오른쪽에 있을 시
isRedFirst = true;
else
isRedFirst = false;
}
// 좌로 이동하는 경우
else {
if(rx < bx) // 빨간 공이 더 왼쪽에 있을 시
isRedFirst = true;
else
isRedFirst = false;
}
}
// 빨간 공 혹은 파란 공을 굴린다.
for(int idx = 0; idx < 2; idx++) {
if(isRedFirst) {
// 빨간 공을 굴리기 시작
y = ry;
x = rx;
while(true) {
ry += dy[curD];
rx += dx[curD];
// 벽이나 다른 색의 공을 만나면
if(!isIn(ry,rx) || mBoard[ry][rx] == 'B' || board[ry][rx] == '#') {
ry -= dy[curD];
rx -= dx[curD];
mBoard[y][x] = '.';
mBoard[ry][rx] = 'R';
break;
}
// 구멍에 빠졌을시
if(board[ry][rx] == 'O') {
rH = true;
mBoard[y][x] = '.';
break;
}
}
isRedFirst = false;
}
else {
// 파란 공을 굴리기 시작
y = by;
x = bx;
while(true) {
by += dy[curD];
bx += dx[curD];
// 벽이나 다른 색의 공을 만나면
if(!isIn(by,bx) || mBoard[by][bx] == 'R' || board[by][bx] == '#') {
by -= dy[curD];
bx -= dx[curD];
mBoard[y][x] = '.';
mBoard[by][bx] = 'B';
break;
}
// 구멍에 빠졌을시
if(mBoard[by][bx] == 'O') {
bH = true;
mBoard[y][x] = '.';
break;
}
}
isRedFirst = true;
}
}
// 파란공이 빠지면 바로 종료
if(bH) {
return -1;
}
// 빨간 공이 만나면, 종료하고 몇번 기울렸는지 횟수를 기록
if(rH) {
return i + 1;
}
}
return -1;
}
public static boolean isIn(int y, int x){
if(y < 0 || y == n || x < 0 || x == m)
return false;
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
난이도
⭐⭐⭐★★
후기
구현 문제였으며, 반례를 통해 오류를 많이 찾은 것 외에는 큰 어려움이 없던 문제였다.
개선할 점
없
