Compy's Blog
458 words
2 minutes
[BOJ] 구슬 탈출
2025-03-17

구슬 탈출

TimeLimitMemoryLimitConditionTAG
2s512MB(3 ≤ N, M ≤ 10)BFS

아니 솔브드 스트릭이 끊겼는데 뭔 오륜지 모르겠네요… ㅠㅜ

하튼 구슬 탈출 시리즈는 그냥 우려먹기 인듯합니다

정답 코드
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;

int inf = 1e9+7;

int n ,m;

char board[11][11];
bool visited[11][11][2]; // 0 is red, 1 is blue



pair<pair<int, int>, bool> move(int dx, int dy, int y, int x, pair<int, int> current){
    queue<pair<int ,int>> q;
    q.push({y, x});
    
    pair<int, int> last;
    
    bool check = false;
    
    while(!q.empty()){
        
        auto [cy, cx] = q.front(); q.pop();
        last= {cy, cx};
        
        if(board[cy][cx] == 'O') return {last, false};
        
        if(cy == current.first && cx == current.second) check = true;
        
        int nx = cx + dx;
        int ny = cy + dy;
        
        if(0 <= ny && ny < n && 0 <= nx && nx < m && board[ny][nx] != '#') q.push({ny, nx});
        
    }
    
    last.first += dy * -1 *  check;
    last.second += dx * -1 *  check;
    
    
    return {last, check};
    
}

int solution(pair<int, int> red_ball, pair<int, int> blue_ball){
    
    queue<pair<int, int>> balls;
    
    
    int dy[] = {1, -1, 0, 0}, dx[] = {0, 0, 1, -1};
    
    
    // 근데 뭐가 먼저 움직이는가.. 이게 중요하거든 blue 부터
    
    balls.push(blue_ball);
    balls.push(red_ball);
    visited[red_ball.first][red_ball.second][0] = true;
    visited[blue_ball.first][blue_ball.second][1] = true;
    
    
    
    int step = 0;
    while(++step <= 10){
        int length = balls.size();
        
        
        bool hole_check = false;
        
        vector<pair<int, int>> update;
        
        while(length > 0){
            pair<int, int> blue = balls.front(); balls.pop();
            pair<int, int> red = balls.front(); balls.pop();

            for(int i = 0; i < 4; i++){
                auto [blue_move, blue_check] = move(dx[i], dy[i], blue.first, blue.second, red);
                
                if(board[blue_move.first][blue_move.second] == 'O') continue;
                
                auto [red_move, red_check] = move(dx[i], dy[i], red.first, red.second, blue);
                
                if(board[red_move.first][red_move.second] == 'O') return step;
                
                balls.push(blue_move);
                balls.push(red_move);
            }
            length-=2;
        }
        
//
//        cout << "\n";
//        for(int i = 0; i < n; i++){
//            for(int j = 0; j < m; j++){
//                cout << visited[i][j][0] << " ";
//            }
//            cout << "\n";
//        }
//        cout << "\n";
    }
    
    return -1;
    
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    
    
    pair<int, int> red_ball, blue_ball, hole;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
            
            if(board[i][j] == 'B') blue_ball = {i, j};
            else if(board[i][j] == 'R') red_ball = {i, j};
            else if(board[i][j] == 'O') hole = {i, j};
        }
    }
    // 그렇네.. 허헣 아 그러면
    
    bool check = solution(red_ball, blue_ball) != -1;
    cout << check;
    
    return 0;
}

[BOJ] 구슬 탈출
https://compy07.github.io/Blog/posts/boj/13459/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-03-17