[BOJ 13460] 구슬 탈출2
업데이트:
문제
- BOJ 13460
- 문제의 저작권은 Baekjoon Online Judge에 있습니다.
접근방식
파란공 빨간공 주어지고 이중에서 빨간공 출구에 들어갈 때 걸리는 이동횟수를 구하는 문제이다.
문제의 조건이 여러개 주어지는데 고려해야할 사항은 다음과 같다.
- 이동횟수는 10회가 넘으면 안된다.
- 빨간공만 출구로 나올 수 있다. 파란공과 동시에 나오거나 파란공만 나오면 -1을 출력한다.
- 빨간공과 파란공이 동시에 같은 위치에 있어서는 안된다.
빨간공과 파란공은 기울기대로 동시에 이동하며 구슬은 한 칸을 차지한다.
동시에 이동해야 한다는 조건이 있어 코드 구현하는데 생각을 오래 했는데, 파란공과 빨간공이 동시에 출구로 빠져나오면 안된다는 조건을 고려해서 파란공먼저 이동시킨 후, 빨간공을 이동시켜서 마지막에 도착한 두 좌표를 비교해주는식으로 문제에 접근했다.
- 빨간공과 파란공의 좌표를 큐에 넣는다.
- 큐에서 하나 꺼내서 각각의 위치에서의 방문정보를 표시해주기 위해 만든 4차원 배열
visited에 방문표시(true)를 해준다. - 큐에서 꺼낸 현재 공의 이동횟수인
now.cnt가 10회를 넘으면 탐색을 종료한다. - 4방향 탐색으로 파란공과 빨간공 각각을 벽에 닿을때까지 이동시킨다.
4-1. 파란공 먼저while문을 돌면서 벽에 닿을때 까지 이동시킨다. 만약 구멍을 만나면 다음 방향으로 넘어간다.
4-2. 빨간공도while문을 돌면서 벽에 닿을 때까지 이동시킨다.만약 구멍을 만나면 중지한다.
4-3. 모든 이동 후, 만약 파란공의 좌표값이 ‘O’이면 탐색을 종료하고 -1을 출력한다.
4-4. 빨간공의 좌표값만 ‘O’이면 탐색을 종료하고 이동횟수를 하나 증가시켜서 답을 출력한다. - 빨간공과 파란공의 좌표가 같다면 현재 이동방향
d에 따라 초기 위치인now.ri,now.rj와now.bi,now.bj의 상하 또는 좌우관계를 따져서 위치를 다시 재조정한다. - 현재 빨간공과 파란공의 위치가 아직 방문하지 않은곳이라면 다음 탐색을 위해 큐에 넣는다.
- 만약 모든 탐색이 끝났는데도 중간에 빠져나오지 못했다면 빨간공이 절대 나올 수 없는 경우이므로 -1을 출력한다.
풀다가 3번정도 틀렸습니다가 떴는데, 파란공을 굴릴 때 구멍을 만나는 경우 return조건을 걸어서 다음 방향을 고려하지 못해서였고 마지막까지 빨간공이 나오지 못하는 경우를 생각하지 못했었다.
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 Main {
static int N, M; // 세로, 가로
static char[][] map;
static int[] di = { -1, 0, 1, 0 }; // 상우하좌
static int[] dj = { 0, 1, 0, -1 };
static int Ans;// 최소 횟수
static Queue<Ball> queue;
static boolean[][][][] visited; // 빨강좌표, 파랑좌표
static Ball ball;
static class Ball { // 공 상태 저장
int ri, rj;
int bi, bj;
int cnt; // 이동횟수
public Ball() {
this.cnt = 0;
}
public Ball(int ri, int rj, int bi, int bj, int cnt) {
this.ri = ri;
this.rj = rj;
this.bi = bi;
this.bj = bj;
this.cnt = cnt;
}
}
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());
map = new char[N][M];
ball = new Ball();
visited = new boolean[N][M][N][M];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = input.charAt(j);
if (map[i][j] == 'R') {
ball.ri = i;
ball.rj = j;
map[i][j]='.';
}
if (map[i][j] == 'B') {
ball.bi = i;
ball.bj = j;
map[i][j]='.';
}
}
} // End input
queue = new LinkedList<>();
queue.add(ball);
bfs();
System.out.println(Ans);
}
private static void bfs() {
while (!queue.isEmpty()) {
Ball now = queue.poll();
visited[now.ri][now.rj][now.bi][now.bj] = true;
// 10번 이상
if (now.cnt >= 10) {
Ans = -1;
return;
}
// 1. 방향을 정하고
for (int d = 0; d < 4; d++) {
// 2. 각 공 끝까지 이동
// 파란색
int nbi = now.bi;
int nbj = now.bj;
while (map[nbi + di[d]][nbj + dj[d]] != '#') {
nbi += di[d];
nbj += dj[d];
if (map[nbi][nbj] == 'O') { // 파란공이 구멍이면 이동중지
break;
}
} // End blue
// 빨간색
int nri = now.ri;
int nrj = now.rj;
while (map[nri + di[d]][nrj + dj[d]] != '#') {
nri += di[d];
nrj += dj[d];
if (map[nri][nrj] == 'O') { // 빨간공이 구멍이면
break;
}
} // End Red
if(map[nbi][nbj] == 'O') continue;
if(map[nri][nrj] == 'O') {
Ans = now.cnt + 1;
return;
}
// 빨간공과 파란공이 동시에 같은 위치에 있을 때
if (nri == nbi && nrj == nbj) {
//방향에 따라서
switch(d) {
case 0: //상
if(now.ri > now.bi) nri += 1;
else nbi += 1;
break;
case 1: //우
if(now.rj < now.bj) nrj -= 1;
else nbj -= 1;
break;
case 2: //하
if(now.ri < now.bi) nri -= 1;
else nbi -= 1;
break;
case 3: //좌
if(now.rj > now.bj) nrj += 1;
else nbj += 1;
break;
}
}
// 빨간공, 파란공 모두 아직 방문하지 않은 위치라면
if (!visited[nri][nrj][nbi][nbj]) {
// 다음 방향 탐색
queue.add(new Ball(nri, nrj, nbi, nbj, now.cnt + 1));
}
}
}//End 탐색
//모든 방향을 탐색했는데도 빠져나오지 못했다면
Ans = -1;
}
}