[백준] 13460 - 구슬 탈출 2

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

13460번: 구슬 탈출 2

브루트포스로 해결할 수 있는 문제

 

문제 자체는 간단하나 조건이 많아 구현 과정에서 실수가 발생할 확률이 높은 문제.

틀렸을 경우에는 빠진 조건이 없는지 다시 한 번 읽어보자.

개인적으로는 코드가 길어지더라도 명확하게 작성하는 것이 오류를 찾는 것에 도움이 된다.

 

구슬의 충돌은 어떤 순서로 구슬을 움직이냐에 따라 발생 할 수도, 안 할 수도 있으므로 번갈아가며 2회 움직여 해결하였다.

 

혹시 틀렸을 경우 아래 블로그에 test case를 100개 작성해 놓으신 분께 감사하며 정답을 확인해보자.

https://boohyunsik.github.io/exit-marble-test-case/

백준) 구슬 탈출2 TC

 

<C++ 코드>

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
 
// 현재 상태를 저장하는 구조체 (회전 횟수, 붉은 공 위치, 푸른 공 위치)
struct stat{
    int num;
    pair<int, int> r;
    pair<int, int> b;
};
 
int main(){
    int n, m;
    pair<int, int> r, b, h;
    char board[11][11] = {};
    int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, -1, 0, 1};
    // 인덱스는 순서대로 red y, red x, blue y, blue x
    bool vis[11][11][11][11] = {};
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        scanf("%s", &board[i]);
        for(int j=0; j<m; j++){
            if(board[i][j] == 'B') b = make_pair(i, j);
            else if(board[i][j] == 'R') r = make_pair(i, j);
        }
    }
 
    // bfs
    queue<stat> q;
    // 초기값 설정
    stat start = {0, r, b};
    vis[start.r.first][start.r.second][start.b.first][start.b.second] = true;
    q.push(start);
    // 순회
    while(!q.empty()){
        // 각 방향 순회
        for(int d=0; d<4; d++){
            stat tmp = q.front();
            bool collision_red = false, collision_blue = false;
            bool red_in = false, blue_in = false;
            // r 먼저 이동
            while(true){
                int ay = tmp.r.first + dy[d];
                int ax = tmp.r.second + dx[d];
                // 벽 만날 시 이동 종료
                if(board[ay][ax] == '#'){
                    break;
                }
                // 파란공과 충돌 시, 나중에 다시 이동
                else if(ay == tmp.b.first && ax == tmp.b.second){
                    collision_red = true;
                    break;
                }
                // 구멍 들어갈 시, 표시
                else if(board[ay][ax] == 'O'){
                    tmp.r.first = -1;
                    red_in = true;
                    break;
                }
                tmp.r.first += dy[d];
                tmp.r.second += dx[d];
            }
 
            // b 이동
            while(true){
                int ay = tmp.b.first + dy[d];
                int ax = tmp.b.second + dx[d];
                // 벽 만날 시 이동 종료
                if(board[ay][ax] == '#'){
                    break;
                }
                // 빨간공과 충돌 시, 나중에 다시 이동
                else if(ay == tmp.r.first && ax == tmp.r.second){
                    collision_blue;
                    break;
                }
                // 구멍 들어갈 시, 실패
                else if(board[ay][ax] == 'O'){
                    blue_in = true;
                    break;
                }
                tmp.b.first += dy[d];
                tmp.b.second += dx[d];
            }
 
            // r 이 b에 걸려서 멈출 시, r 다시 이동
            while(collision_red){
                int ay = tmp.r.first + dy[d];
                int ax = tmp.r.second + dx[d];
                // 벽 만날 시 이동 종료
                if(board[ay][ax] == '#'){
                    break;
                }
                // 파란공과 충돌 시, 정지
                else if(ay == tmp.b.first && ax == tmp.b.second){
                    break;
                }
                // 구멍 들어갈 시, 프로그램 종료
                else if(board[ay][ax] == 'O'){
                    tmp.r.first = -1;
                    red_in = true;
                    break;
                }
                tmp.r.first += dy[d];
                tmp.r.second += dx[d];
            }
            // b 다시 이동
            while(collision_blue){
                int ay = tmp.b.first + dy[d];
                int ax = tmp.b.second + dx[d];
                // 벽 만날 시 이동 종료
                if(board[ay][ax] == '#'){
                    break;
                }
                // 빨간공과 충돌 시, 나중에 다시 이동
                else if(ay == tmp.r.first && ax == tmp.r.second){
                    break;
                }
                // 구멍 들어갈 시, 실패
                else if(board[ay][ax] == 'O'){
                    blue_in = true;
                    break;
                }
                tmp.b.first += dy[d];
                tmp.b.second += dx[d];
            }
 
            if(blue_in){
                continue;
            }
 
            if(red_in){
                printf("%d", tmp.num + 1);
                return 0;
            }
            if(!vis[tmp.r.first][tmp.r.second][tmp.b.first][tmp.b.second]){
                vis[tmp.r.first][tmp.r.second][tmp.b.first][tmp.b.second] = true;
                stat new_stat = {tmp.num + 1, tmp.r, tmp.b};
                q.push(new_stat);
            }
        }
        stat tmp = q.front();
        if(tmp.num > 9){
            break;
        }
        q.pop();
    }
    // 10회 이내에 해결 불가능
    printf("-1");
    return 0;
}