Java
보드의 가로, 세로 길이
보드의 상태
빨간 구슬을 탈출시키기 위해 기울어야 하는 최소한의 횟수
이 문제의 키 포인트는 다음과 같다.
따라서 다음 idea에 초점을 둬가며 코드를 짜였다.
구슬 각각의 시작 위치를 기준으로 동, 서, 남, 북으로 기울였을 때 움직일 수 있는지, 구멍에 빠지는 지를 조사하여야 한다. 만약 구멍에 빠지지 않고, 해당 방향으로 기울일 수 있는 상태라면 그 위치에 대해 다시 기울여 보면 된다.
따라서 bfs를 이용하여 구멍에 빠지지 않고 기울일 수 있는 상태일 경우 queue에 넣어주도록 한다.
파란 구슬과 빨간 구슬을 동시에 움직여 주어야 하므로 queue에 넣을 때는 새로운 class를 생성해주어 (필자가 작성한 코드에서는 position으로 칭하였다) 빨간 구슬의 x,y 좌표 그리고 파란 공의 x,y 좌표를 모두 넣을 수 있도록 한다.
빨간 공이 구멍에 빠지더라도 이후 파란 공이 구멍에 빠진다면 해당 결과는 fail이 될 것이다. 따라서 공이 겹치는지 조사는 빨간 구슬이 구멍에 빠지지 않을 때만 해주도록 하였다.
import java.io.*;
import java.util.*;
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 class Main {
public static char board[][];
public static int now[][];
public static int hole_X = 0, hole_Y = 0;
public static int red_X, red_Y, blue_X, blue_Y;
public static int row, col;
public static int min = Integer.MAX_VALUE;
public static int[] dx = {-1,0,1,0};
public static int[] dy = {0,-1,0,1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine();
String[] sp = str.split(" ");
row = Integer.parseInt(sp[0]);
col = Integer.parseInt(sp[1]);
//board 모양 저장
board = new char[row][col];
now = new int[row][col];
for(int i = 0; i<row;i++) {
str = br.readLine();
for(int j = 0; j<col;j++) {
board[i][j] = str.charAt(j);
//구멍의 x와 y 좌표를 담는다.
if(board[i][j] == 'O') {
hole_X = i;
hole_Y = j;
}
//빨간 구슬의 위치를 저장
else if(board[i][j] == 'R') {
red_X = i;
red_Y = j;
}
//파란 구슬의 위치를 저장
else if(board[i][j] == 'B') {
blue_X = i;
blue_Y = j;
}
//벽은 갈 수 없는 보드
if(board[i][j] == '#')
now[i][j] = 0;
//나머지는 갈 수 있는 보드
else now[i][j] = 1;
}
}
bfs();
if (min <= 10) bw.write(min+"");
else bw.write(-1+"");
bw.flush();
}
public static void bfs() {
boolean red_flag = false;
boolean blue_flag = false;
boolean move_flag = false; //해당 방향으로 움직여도 될지를 정함
boolean redHole;
boolean blueHole;
Queue<position> q= new LinkedList<>();
q.add(new position(red_X,red_Y,blue_X,blue_Y,0)); //빨간 공의 위치를 q에 담는다.
while(!q.isEmpty()) {
//현재 빨간 공과 파란 공의 위치를 꺼낸다.
position curr = q.poll();
//각각의 좌표를 저장한다.
int rX,rY,bX,bY;
int now_cnt = curr.cnt;
//현재 방향에서 동서남북으로 움직여 본다.
for(int i = 0; i< 4; i++) {
// red_flag는 벽을 만나면 움직임을 멈춘다.
// blue_flag는 벽을 만나면 움직임을 멈춘다.
// 만약 둘 다 움직임을 멈추면 기울임을 멈추는 것이며 그때까지 이상이 없으면
// 이 최종 좌표를 다시 q에 넣어준다.
red_flag = false;
blue_flag = false;
redHole = false;
blueHole = false;
rX = curr.redx;
rY = curr.redy;
bX = curr.bluex;
bY = curr.bluey;
//기울여 준다.
while(true) {
//두 공 모두 더이상 움직일 수 없다면 기울이기를 멈춘다.
if(red_flag == true && blue_flag == true) break;
//다음 움직일 방향이 벽이라면 더이상 움직이지 않도록 red_flag를 바꿔준다
if(now[rX+dx[i]][rY+dy[i]] == 0)
red_flag = true;
if(now[bX+dx[i]][bY+dy[i]] == 0)
blue_flag = true;
//다음 움직일 방향에 두 공이 겹친다면
//더 이상 기울이지 않도록 한다.
if((rX == bX + dx[i] && rY == bY+dy[i] && !redHole) || (bX == rX+dx[i] && bY == rY+dy[i])) {
if(red_flag == true) blue_flag = true;
else if (blue_flag == true) red_flag = true;
}
if(red_flag == false) {
rX += dx[i];
rY += dy[i];
}
if(blue_flag == false) {
bX += dx[i];
bY += dy[i];
}
//만약 움직인 방향이 구멍이라면
if(bX == hole_X && bY == hole_Y) {
blueHole = true;
break; // 더 이상 진행할 필요가 없어진다.
}
if(rX == hole_X && rY == hole_Y) {
redHole = true;
red_flag = true;
}
}
//파란 공이 빠졌을 경우 무조건 fail
if(blueHole) continue;
//빨간 공이 탈출하면서 파란 공은 탈출하지 못할 경우 success!!
if(redHole && !blueHole) {
min = Math.min(min, now_cnt+1);
}
//횟수가 10번이 넘게 될 경우 더 이상 q에 넣지 않고 count를 하지 않도록 한다.
else if(now_cnt + 1 > 10) {
continue;
}
// 빨간 공이 hole에 도달하지 않고
// 움직일 수 있다면 각각의 좌표와 기울인 횟수를 position에 넣어준다.
else q.add(new position(rX,rY,bX,bY,now_cnt+1));
}
}
}
}