BOJ 13460 · 구슬 탈출 2

알고리즘 분류 : BFS  

구슬 탈출 시리즈 두 번째 문제다. 첫 번째 문제인 '구슬 탈출'을 풀었으면, 이 문제는 쉽게 해결할 수 있다. 출력값만 바꾸면 된다. 자세한 내용은 이전 문제 참조.

• 10번 이하로 탈출 실패 시, -1을 출력한다.
• 탈출 성공 시, 움직인 횟수를 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct bead {
    int rx, ry, bx, by, d;
};

int n, m;
char a[10][10];
bool check[10][10][10][10];
queue<bead> q;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void move(int &x, int &y, int &c, int dx, int dy) {
    while (a[x+dx][y+dy] != '#' && a[x][y] != 'O') {
        x += dx;
        y += dy;
        c += 1;
    }
}

void bfs() {
    while (!q.empty()) {
        int rx = q.front().rx, ry = q.front().ry;
        int bx = q.front().bx, by = q.front().by;
        int d = q.front().d; q.pop();
        if (d >= 10) break;
        for (int i=0; i<4; i++) {
            int nrx = rx, nry = ry, nbx = bx, nby = by;
            int rc = 0, bc = 0, nd = d+1;
            move(nrx, nry, rc, dx[i], dy[i]);
            move(nbx, nby, bc, dx[i], dy[i]);
            if (a[nbx][nby] == 'O') continue;
            if (a[nrx][nry] == 'O') {
                printf("%d\n", nd);
                return;
            }
            if (nrx == nbx && nry == nby) {
                if (rc > bc) nrx -= dx[i], nry -= dy[i];
                else nbx -= dx[i], nby -= dy[i];
            }
            if (check[nrx][nry][nbx][nby]) continue;
            check[nrx][nry][nbx][nby] = true;
            q.push({nrx, nry, nbx, nby, nd});
        }
    }
    printf("-1\n");
}

int main() {
    scanf("%d %d", &n, &m);
    int rx = 0, ry = 0, bx = 0, by = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%1s", &a[i][j]);
            if (a[i][j] == 'R') rx = i, ry = j;
            else if (a[i][j] == 'B') bx = i, by = j;
        }
    }
    q.push({rx, ry, bx, by, 0});
    check[rx][ry][bx][by] = true;
    bfs();
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
check = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
q = deque()

def init():
    _rx, _ry, _bx, _by = [0]*4
    for i in range(n):
        for j in range(m):
            if a[i][j] == 'R':
                _rx, _ry = i, j
            elif a[i][j] == 'B':
                _bx, _by = i, j
    q.append((_rx, _ry, _bx, _by, 0))
    check[_rx][_ry][_bx][_by] = True

def move(_x, _y, _dx, _dy, _c):
    while a[_x+_dx][_y+_dy] != '#' and a[_x][_y] != 'O':
        _x += _dx
        _y += _dy
        _c += 1
    return _x, _y, _c

def bfs():
    while q:
        rx, ry, bx, by, d = q.popleft()
        if d >= 10:
            break
        for i in range(4):
            nrx, nry, rc = move(rx, ry, dx[i], dy[i], 0)
            nbx, nby, bc = move(bx, by, dx[i], dy[i], 0)
            if a[nbx][nby] == 'O':
                continue
            if a[nrx][nry] == 'O':
                print(d+1)
                return
            if nrx == nbx and nry == nby:
                if rc > bc:
                    nrx, nry = nrx-dx[i], nry-dy[i]
                else:
                    nbx, nby = nbx-dx[i], nby-dy[i]
            if not check[nrx][nry][nbx][nby]:
                check[nrx][nry][nbx][nby] = True
                q.append((nrx, nry, nbx, nby, d+1))
    print(-1)

init()
bfs()

---

참고

• 백준 온라인 저지 : BOJ 13460
• 구슬 탈출