문제
N×M 크기의 보드에 빨간 구슬(R)과 파란 구슬(B)이 하나씩 있다. 보드를 기울여 구슬을 움직일 수 있으며, 한 번 기울이면 구슬은 벽(#)에 닿을 때까지 이동한다. 구멍(O)을 통해 빨간 구슬만 탈출시키는 최소 기울임 횟수를 구하는 문제다. 10번 이내에 탈출할 수 없으면 -1을 출력한다.
입력
- 첫째 줄: 보드 크기 N M (3 ≤ N, M ≤ 10)
- 다음 N줄: 보드 상태 (
.: 빈칸,#: 벽,O: 구멍,R: 빨간 구슬,B: 파란 구슬)
출력
최소 기울임 횟수 (10번 초과 또는 불가능하면 -1)
예제
| 입력 | 출력 |
|---|---|
5 5 ##### #..O# #.#.# #RB.# ##### | 4 |
풀이
BFS로 빨간/파란 구슬의 위치 상태를 탐색한다. 두 구슬의 위치를 4차원 방문 배열로 관리하여 중복 상태를 방지한다.
- 초기 빨간 구슬(
R)과 파란 구슬(B)의 위치를 파악하여 BFS 큐에 삽입한다. - 4방향(상하좌우)으로 보드를 기울이는 시뮬레이션을 수행한다.
- 각 방향으로 구슬을 벽에 닿을 때까지 이동시키고, 구멍에 빠지면 이동을 멈춘다.
- 파란 구슬이 구멍에 빠지면 해당 방향은 무효 처리한다.
- 빨간 구슬만 구멍에 빠지면 현재 이동 횟수를 출력하고 종료한다.
- 두 구슬이 같은 위치에 있으면, 이동 방향에 따라 원래 더 뒤에 있던 구슬을 한 칸 뒤로 조정한다.
핵심 아이디어: 두 구슬의 위치를 (rRow, rCol, bRow, bCol) 4개 값으로 표현한 상태 공간에서 BFS를 수행한다. 4차원 방문 배열 visited[10][10][10][10]으로 방문 여부를 관리하고, 10회 초과 시 -1을 반환한다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day37BOJ13460구슬탈출2구현문제bfs { // 13460 구슬탈출 2
static int N, M;
static char[][] map;
static boolean[][][][] visited;
static int[] dr = new int[] { -1, 1, 0, 0 };
static int[] dc = new int[] { 0, 0, -1, 1 };
public static void main(String[] args) throws Exception {
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];
visited = new boolean[10][10][10][10];
Node node = new Node();
node.cnt = 0;
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = str.charAt(j);
if (map[i][j] == 'R') {
node.rIdx = i;
node.rJdx = j;
} else if (map[i][j] == 'B') {
node.bIdx = i;
node.bJdx = j;
}
}
}
bfs(node);
br.close();
}
private static void bfs(Node ball) {
Queue<Node> q = new LinkedList<>();
q.offer(ball);
while (!q.isEmpty()) {
Node node = q.poll();
visited[node.rIdx][node.rJdx][node.bIdx][node.bJdx] = true;
if (node.cnt >= 10) {
System.out.println(-1);
return;
}
for (int dir = 0; dir < 4; dir++) {
int bi = node.bIdx;
int bj = node.bJdx;
while (map[bi + dr[dir]][bj + dc[dir]] != '#') {
bi += dr[dir];
bj += dc[dir];
if (map[bi][bj] == 'O')
break;
}
int ri = node.rIdx;
int rj = node.rJdx;
while (map[ri + dr[dir]][rj + dc[dir]] != '#') {
ri += dr[dir];
rj += dc[dir];
if (map[ri][rj] == 'O')
break;
}
if (map[bi][bj] == 'O') {
continue;
}
if (map[ri][rj] == 'O') {
System.out.println(node.cnt + 1);
return;
}
if (ri == bi && rj == bj) {
switch (dir) {
case 0:
if (node.rIdx > node.bIdx)
ri++;
else
bi++;
break;
case 1:
if (node.rIdx > node.bIdx)
bi--;
else
ri--;
break;
case 2:
if (node.rJdx > node.bJdx)
rj++;
else
bj++;
break;
case 3:
if (node.rJdx > node.bJdx)
bj--;
else
rj--;
}
}
if (!visited[ri][rj][bi][bj]) {
q.offer(new Node(ri, rj, bi, bj, node.cnt + 1));
}
}
}
System.out.println(-1);
}
}
class Node {
int rIdx, rJdx;
int bIdx, bJdx;
int cnt;
public Node() {
}
public Node(int rIdx, int rJdx, int bIdx, int bJdx, int cnt) {
this.rIdx = rIdx;
this.rJdx = rJdx;
this.bIdx = bIdx;
this.bJdx = bJdx;
this.cnt = cnt;
}
}복잡도
- 시간: O(N^2 * M^2) — 두 구슬의 가능한 위치 조합이 상태 공간
- 공간: O(N^2 * M^2) — 4차원 방문 배열 크기