일단 이 문제는 bfs로 푸는 문제이며 주의 해야할 점은
- 구슬이 겹쳤을 때 처리
- 빨강구슬 이동거리와 파랑구슬 이동거리를 비교하여 처리하였다.
자세한 설명은 밑 코드에 주석으로 남겼습니다.
- 빨강구슬 이동거리와 파랑구슬 이동거리를 비교하여 처리하였다.
- 구멍으로 빠져나갔을 때 처리
- 마찬가지로 주석에 남겼습니다.
위 두가지만 조심하면 엄청 어려운 문제까지는 아니었다.
하지만 처음에 이해를 못해서 다른 사람들이 푼 코드를 봤는데 푸는 방식이 좀 여려가지로 나뉘어서 이해를 하지 못하다가 결국 하나하나 코드를 디버깅하면서 이해하고 나의 방식대로 다시 코드를 작성하였다.
- 주석에 설명 자세히 남겼습니다.
문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력
파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 1을 없으면 0을 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Test13459 {
static int n, m;
// 구슬판 문자를 받을 2차원 배열
static char[][] board;
// 움직여야할 x, y 좌표
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
//방문 체크 배열 (빨강구슬, 파랑구슬을 동시에 담기위해서 4차원 배열을 사용)
static boolean[][][][] visit;
static Queue<Position> Q;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
int redX =0, redY=0, blueX=0, blueY=0;
board = new char[n][m];
visit = new boolean[n][m][n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < str.length(); j++) {
char ch = str.charAt(j);
board[i][j] = ch;
if (ch == 'R') {
//빨강구슬을 발견하면 좌표값을 저장한다.
redX = i;
redY = j;
}
if (ch == 'B') {
// 파랑구슬을 발견하면 변수에 좌표값을 저장한다.
blueX = i;
blueY = j;
}
}
}
// bfs를 돌리기 위해 큐를 만든다.
Q = new LinkedList<>();
// 찾은 초기 구슬들의 위치를 변수에 담아준다.
// 처음에 횟수를 1로 넣어주는 이유는 bfs를 돌릴때 횟수증가를 맨 나중에 하기 때문이다.
// 만약 횟수를 증가하기전에 리턴이 된다면 횟수가 한번 부족해지기 때문에 1을 초기값으로 설정해주어야 한다.
Position position = new Position(redX, redY, blueX, blueY, 1);
// 초기 구슬들의 방문여부를 참으로 설정한다.
visit[redX][redY][blueX][blueY] = true;
// 큐에 초기구슬들의 위치를 담은 변수를 넣어주고 bfs를 돌린다.
Q.offer(position);
System.out.println(bfs());
}
public static int bfs(){
while (!Q.isEmpty()){
Position tmp = Q.poll();
// 만약 횟수가 10번 이상이라면 0을 반환
if (tmp.cnt > 10) return 0;
// for문을 돌면서 판별한다.
for (int i = 0; i < 4; i++) {
// 판을 기울려서 구슬을 움직이고 그 구슬 위치를 변수에 담아준다.
Marble redMarble = move(tmp.redX, tmp.redY, i, 0);
Marble blueMarble = move(tmp.blueX, tmp.blueY, i, 0);
int nRedX = redMarble.X;
int nRedY = redMarble.Y;
int nRedDis = redMarble.dis;
int nBlueX = blueMarble.X;
int nBlueY = blueMarble.Y;
int nBlueDis = blueMarble.dis;
// 만약 파란 구슬의 위치가 O라면 밑 과정을 생략하고 넘어간다.
// 파란 구슬을 먼저 판별하는 이유는 동시에 구멍에 빠지는 경우든 파란구슬이 구멍에 빠지는 경우든
// 파란구슬이 구멍에 빠지기 때문에 먼저 판별을 하면 동시에 빠지는 경우도 체크할수 있다.
if (board[nBlueX][nBlueY] == 'O') continue;
// 빨강 구슬이 구멍에 들어가면 1을 반환한다.
// 여기서 아까 초기 횟수를 1로 설정한 이유가 나온다.
// 만약 초기 횟수를 0으로 했다면 0번움직였는데 구슬이 구멍에 들어가는 경우가 생긴다.
if (board[nRedX][nRedY] == 'O'){
return 1;
}
//만약 구슬의 위치가 같다면 구슬의 이동거리를 비교해 처리한다.
if (nRedX == nBlueX && nRedY == nBlueY){
//만약 빨강구슬의 이동거리가 더 길다면 빨강구슬이 한번더 움직인 상황이기 때문에
//빨강 구슬의 위치를 한번 이동한 반대방향으로 이동시켜준다.
if (nRedDis> nBlueDis){
nRedX -= dx[i];
nRedY -= dy[i];
}
// 파란구슬의 이동거리가 처리해준다.
else if(nBlueDis > nRedDis){
nBlueX -= dx[i];
nBlueY -= dy[i];
}
}
// 만약 빨강구슬과 파랑구슬의 위치가 방문했었다면 큐에 담지 않고 생략한다.
if (visit[nRedX][nRedY][nBlueX][nBlueY]) continue;
// 아닌경우 구슬들의 위치를 true로 설정하고 큐에 넣어준다.
visit[nRedX][nRedY][nBlueX][nBlueY] = true;
Q.offer(new Position(nRedX, nRedY, nBlueX, nBlueY, tmp.cnt+1));
}
}
return 0;
}
// 구슬판을 기울여서 구슬들의 위치를 반환하는 함수
public static Marble move(int x, int y, int i, int dis){
// 다음에 이동할 구슬위치가 '#' 이 아니고 현재 구슬위치가 구멍이 아닐때 이동시켜준다.
while (board[x+dx[i]][y+dy[i]] != '#' && board[x][y] != 'O'){
x += dx[i];
y += dy[i];
dis +=1;
}
// 구슬판을 기울여 이동한 구슬의 좌표값과 이동한 거릴를 반환한다.
return new Marble(x, y, dis);
// 위의 반복문을 풀어서 하면 이렇게 된다.
/*
while (true){
// 좌표값과 이동거리를 일단 더해주고
x += dx[i];
y += dy[i];
dis +=1;
// 벽을 만나면 이동했던 방향 반대로 다시 이동시키고 이동거리도 -1해준다.
if (board[x][y] == '#'){
x -= dx[i];
y -= dy[i];
dis -= 1;
return new Marble(x, y, dis);
}
// 만약 구멍을 만나면 현재 좌표값과 이동거리를 반환해준다.
else if (board[x][y] == 'O') {
return new Marble(x, y, dis);
}
}
*/
}
// 빨강구슬과 파랑구슬 그리고 횟수를 담는 클래스이다.
public static class Position{
int redX, redY, blueX, blueY, cnt;
public Position(int redX, int redY, int blueX, int blueY, int cnt) {
this.redX = redX;
this.redY = redY;
this.blueX = blueX;
this.blueY = blueY;
this.cnt = cnt;
}
}
// 구슬의 좌표값과 이동한 거리를 담는 클래스이다.
public static class Marble {
int X, Y, dis;
public Marble(int X, int Y, int dis) {
this.X = X;
this.Y = Y;
this.dis = dis;
}
}
}