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

구슬 탈출 3

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

우려먹기 시리즈라 그냥 설명은 첫번째 구슬 탈출 2에서 봐주시면 감사하겠습니다.

정답 코드
#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};
    
}

pair<int, string> solution(pair<int, int> red_ball, pair<int, int> blue_ball){
    
    queue<pair<pair<int, int>, string>> balls;
    
    
    int dy[] = {1, -1, 0, 0}, dx[] = {0, 0, 1, -1};
    
    char direction[] = {'D', 'U', 'R', 'L'};
    // 근데 뭐가 먼저 움직이는가.. 이게 중요하거든 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();
        
        
        
        
        while(length > 0){
            auto [blue, _] = balls.front(); balls.pop();
            auto [red, path] = 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, path+direction[i]};
                
                balls.push({blue_move, ""});
                balls.push({red_move, path + direction[i]});
            }
            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};
        }
    }
    // 그렇네.. 허헣 아 그러면
    
    auto [result, path] = solution(red_ball, blue_ball);
    
    cout << result << "\n";
    if(result >-1) cout << path;
    
    return 0;
}
[BOJ] 구슬 탈출 3
https://compy07.github.io/Blog/posts/boj/15644/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-03-17