BOJ 13460 - 구슬 탈출 2

문제

• \(N \times M(3 \le N,\; M \le 10)\)인 보드의 정보가 아래와 같이 주어진다.
  • . : 빈 칸
  • # : 공이 이동할 수 없는 벽
  • O : 구멍
  • R : 빨간 구슬
  • B : 파란 구슬
  • 보드의 가장자리는 모두 #이다.
  • R, B는 항상 1개씩이다.
• 아래와 같은 규칙으로 보드를 움직일 때, 최소 몇 번의 동작을 통해 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다.
  • 보드를 상하좌우로 기울여서 구슬을 굴려야 한다.
  • 한 번 기울이면 구슬이 움직이지 않을 때까지 그 상태를 유지해야 한다.
  • 빨간 구슬만 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다.
  • 구슬들은 동시에 같은 칸에 있을 수 없다.
  • 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

풀이

• 빨간 구슬의 위치 (ri, rj), 파란 구슬의 위치 (bi, bj)의 좌표 모두 10 미만이기 떄문에, ri*1000+rj*100+bi*10+bj를 vis 배열의 상태공간으로 정의하고 BFS를 수행했다.
• 구슬이 움직이지 않을 때까지 굴리고, 경로에서의 구멍 존재 여부, R, B의 겹침 여부 등을 아래의 손서에 따라 확인하고 각 경우에 대한 처리를 해야 한다.
  • B를 먼저 굴리면서 구멍에 빠지는지 확인
  • R을 굴리며 경로에 구멍이 있는지 확인
    • 구멍이 있는 경우 R이 구멍에 빠지는 시점의 R, B의 좌표를 기준으로 vis 배열의 값을 업데이트
    • 구멍이 없는 경우 R, B의 새로운 좌표를 기준으로 vis 업데이트 후 큐에 넣음

코드

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#define v vector

using namespace std;
using vi = vector<int>;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, s = 0, oi, oj;
    int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};
    vi vis(10000, 100);
    cin >> n >> m;
    v<v<char>> ar(n, v<char>(m, '#'));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> ar[i][j];
            if (ar[i][j] == 'R') {
                s += i * 1000 + j * 100;
                continue;
            }
            if (ar[i][j] == 'B') {
                s += i * 10 + j;
                continue;
            }
            if (ar[i][j] == 'O') {
                oi = i;
                oj = j;
            }
        }
    }
    queue<int> q;
    vis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int cur = q.front(), ri, rj, bi, bj;
        q.pop();
        ri = cur / 1000, rj = cur / 100 % 10, bi = cur / 10 % 10, bj = cur % 10;
        for (int i = 0; i < 4; i++) {
            int nri = ri + di[i], nrj = rj + dj[i], nbi = bi + di[i], nbj = bj + dj[i], ncur, boflag = 0, aoflag = 0;
            while (ar[nbi][nbj] != '#') {
                if (ar[nbi][nbj] == 'O') {
                    boflag = 1;
                    break;
                }
                nbi += di[i];
                nbj += dj[i];
            }
            if (boflag) continue;
            nbi -= di[i];
            nbj -= dj[i];
            while (ar[nri][nrj] != '#') {
                if (ar[nri][nrj] == 'O') {
                    aoflag = 1;
                    if (vis[oi * 1000 + oj * 100 + nbi * 10 + nbj] > vis[ri * 1000 + rj * 100 + bi * 10 + bj] + 1) {
                        vis[oi * 1000 + oj * 100 + nbi * 10 + nbj] = vis[ri * 1000 + rj * 100 + bi * 10 + bj] + 1;
                    }
                    break;
                }
                nri += di[i];
                nrj += dj[i];
            }
            if (aoflag) continue;
            nri -= di[i];
            nrj -= dj[i];
            if (nri == nbi && nrj == nbj) {
                if (di[i] == 0) {
                    if (dj[i] == -1) {
                        if (rj < bj)
                            nbj++;
                        else
                            nrj++;
                    } else {
                        if (rj < bj)
                            nrj--;
                        else
                            nbj--;
                    }
                } else {
                    if (di[i] == -1) {
                        if (ri < bi)
                            nbi++;
                        else
                            nri++;
                    } else {
                        if (ri < bi)
                            nri--;
                        else
                            nbi--;
                    }
                }
            }
            ncur = nri * 1000 + nrj * 100 + nbi * 10 + nbj;
            if (vis[ncur] > vis[cur] + 1) {
                vis[ncur] = vis[cur] + 1;
                q.push(ncur);
            }
        }
    }
    s = 100;
    for (int i = oi * 1000 + oj * 100 + 11; i < oi * 1000 + oj * 100 + 99; i++) {
        if (vis[i] < s) s = vis[i];
    }
    if (s > 10)
        cout << -1;
    else
        cout << s;
    return 0;
}

풀고나서

• BFS를 사용해서 DFS를 사용하는 풀이보다 메모리를 더 사용했다.