백준) 13460 구슬 탈출 2 // 구 째로탈출2

구슬 탈출 2 

보드에 빨간 공과 파란 공을 올려 두고, 보드를 4방향으로 기울여보면서 빨간 공을 보드의 구멍으로 탈출시키는게 목표다.

이 때 가장 적게 기울여보는 횟수는 얼마나 될까?

https://www.acmicpc.net/problem/13460

맵이 어떻게 주어질지 모르기 때문에 다 해보는 완전탐색이 필요하다. 동시에 최소 횟수를 요구하므로 bfs가 적당하다.

참고로 진짜 모든 경우를 탐색해보는 방법으로도 통과가 가능하긴 하다. 시간이 더 걸리긴 하지만..

공이 두 개씩 굴러다니므로 visit 확인을 두 공의 좌표를 모두 확인해야 한다는 점을 유의해야 한다.

규칙이 조금 까다로운데, 분기를 다음과 같이 할 수 있다.

1. 일단 상대 공을 무시하고 두 공을 굴려서 어디로 가는지 확인한다.

2. 만약 파란 공이 구멍에 빠지면 이 경우는 글러먹은 경우니까 버린다.

3. 두 공이 겹칠 경우도 있다. 이 때는 굴리기 전의 좌표를 보고 잘 조정해줘야 한다. 아래로 굴렸고 겹쳤는데, 원래 빨간공이 위에 있었다면 빨간공을 파란공 위로 옮겨 줘야한다.

친절하게도 10을 초과하는 답은 원하지 않는다니까 4 ^ 10 안에 수행가능하다. 물론 한 번 굴리고, 다음번에 또 같은 방향으로 굴리는 경우 visit확인을 통해 가지치기가 되니까 훨씬 빠르게 문제가 풀린다.

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
 
struct balls {
    int depth;
    int rx, ry, bx, by;
};
int irx, iry, ibx, iby, hx, hy;
 
int n, m, ans = -1;
int map[10][10];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
bool visit[10][10][10][10];
char str[11];
 
void move(int& x, int& y, int d) {
    while (1) {
        x += dir[d][0]; y += dir[d][1];
        if (map[x][y] == 1) {
            x -= dir[d][0]; y -= dir[d][1];
            break;
        }
        else if (map[x][y] == 2)
            break;
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", str);
        for (int j = 0; j < m; ++j) {
            switch (str[j]) {
            case '.':
                map[i][j] = 0; break;
            case '#':
                map[i][j] = 1; break;
            case 'O':
                map[i][j] = 2; hx = i, hy = j; break;
            case 'R':
                irx = i, iry = j; break;
            case 'B':
                ibx = i, iby = j; break;
            }
        }
    }
 
    queue<balls> q;
    q.push({ 0,irx,iry,ibx,iby });
    visit[irx][iry][ibx][iby] = true;
 
    while (!q.empty()) {
        balls cur = q.front(); q.pop();
 
        if (cur.depth > 10)
            break;
        if (cur.rx == hx && cur.ry == hy) {
            ans = cur.depth;
            break;
        }
 
        for (int i = 0; i < 4; ++i) {
            int rx = cur.rx, ry = cur.ry;
            int bx = cur.bx, by = cur.by;
            move(rx, ry, i), move(bx, by, i);
 
            if (bx == hx && by == hy)
                continue;
 
            if (rx == bx && ry == by) {
                switch (i) {
                case 0:
                    cur.rx < cur.bx ? rx-- : bx--; break;
                case 2:
                    cur.rx < cur.bx ? bx++ : rx++; break;
                case 1:
                    cur.ry < cur.by ? ry-- : by--; break;
                case 3:
                    cur.ry < cur.by ? by++ : ry++; break;
                }
            }
 
            if (!visit[rx][ry][bx][by]) {
                balls next = { cur.depth + 1,rx,ry,bx,by };
                q.push(next);
                visit[rx][ry][bx][by] = true;
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}