[삼성SW테스트] 백준 13460번 - 구슬 탈출 2 (정답률 24%)

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

13460번: 구슬 탈출 2

삼성 SW테스트 기출문제다. (유형: BFS)

 

어차피 관심있는 것은 공들의 위치이므로 공들의 위치와 depth를 관리하는 구조체를 큐에 넣고 BFS 탐색을 하면 된다.

 

왜냐하면 최소 회전 횟수를 구하는 문제이므로, DFS처럼 한 경우에 대해 모두 다 해보는 것 보다는 동시에 depth를 확장시켜나가다가 답을 찾으면 종료하는 편이 더욱 효율적이기 때문이다.

 

아래는 소스코드 (0ms)

 

#include <iostream>
#include <queue>
#include <string>
#define maxlen 10
using namespace std;
int n, m, ans = -1;
int map[maxlen][maxlen];
int irx, iry, ibx, iby, hx, hy;
int dr[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
bool visit[10][10][10][10];
 
typedef struct balls{
    int depth;
    int rx, ry, bx, by;
};
 
void move(int &x, int &y, int dir){
    while (1){
        x += dr[dir][0]; y += dr[dir][1];
        if (map[x][y] == 1){
            x -= dr[dir][0]; y -= dr[dir][1];
            break;
        }
        else if (map[x][y] == 2)
            break;
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string str;
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> str;
        for (int j = 0; j < str.length(); 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;
            }
        }
    }
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            for (int k = 0; k < 10; k++)
                for (int z = 0; z < 10; z++)
                    visit[i][j][k][z] = false;
 
    queue<balls> q;
    balls first; first.depth = 0; first.rx = irx; first.ry = iry; first.bx = ibx; first.by = iby;
    q.push(first);
    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:
                    //East
                    cur.ry > cur.by ? by-- : ry--; break;
                case 1:
                    // West
                    cur.ry > cur.by ? ry++ : by++; break;
                case 2:
                    //South
                    cur.rx > cur.bx ? bx-- : rx--; break;
                case 3:
                    //North
                    cur.rx > cur.bx ? rx++ : bx++; break;
                }
            }
 
            if (!visit[rx][ry][bx][by]){
                balls next; 
                next.depth = cur.depth+1; next.rx = rx; next.ry = ry; next.bx = bx; next.by = by;
                q.push(next);
                visit[rx][ry][bx][by] = true;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}