[C++]백준 13460번 구슬 탈출2

📌문제 링크

---

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

📌문제 설명

---

기본적인 4방향을 탐색하는 bfs문제의 응용 버전이다. 빨간 구슬과 파란 구슬을 동시에 4방향으로 이동시키며 빨간 구슬만 구멍에 빠뜨리는 최단 경로를 BFS로 탐색한다. 방문 상태를 4차원 배열로 관리하고, 각 이동마다 구슬의 위치를 조정하며, 10회 이내에 목표를 달성하지 못하면 -1을 반환한다. 구슬이 겹치는 경우 더 늦게 이동한 구슬의 위치를 조정하는 로직으로 복잡한 시뮬레이션을 해결한다.

📌코드

---

#include <iostream>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;

const int MAX = 10;
char board[MAX][MAX];
bool visited[MAX][MAX][MAX][MAX];
int N, M;

// 상, 하, 좌, 우 방향
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

// 구슬 위치와 이동 횟수를 저장하는 구조체
struct State {
    int rx, ry, bx, by, cnt;
};

// 구슬을 특정 방향으로 이동시키는 함수
pair<bool, pair<int, int>> move(int x, int y, int dx, int dy) {
    int nx = x, ny = y;
    bool hole = false;
    
    while (board[nx + dx][ny + dy] != '#') {
        nx += dx;
        ny += dy;
        if (board[nx][ny] == 'O') {
            hole = true;
            break;
        }
    }
    
    return {hole, {nx, ny}};
}

int bfs(int rx, int ry, int bx, int by) {
    queue<State> q;
    q.push({rx, ry, bx, by, 0});
    visited[rx][ry][bx][by] = true;
    
    while (!q.empty()) {
        auto [rx, ry, bx, by, cnt] = q.front();
        q.pop();
        
        // 10번 초과하면 실패
        if (cnt >= 10) return -1;
        
        for (int dir = 0; dir < 4; dir++) {
            auto [rHole, redPos] = move(rx, ry, dx[dir], dy[dir]);
            auto [bHole, bluePos] = move(bx, by, dx[dir], dy[dir]);
            
            int nrx = redPos.first, nry = redPos.second;
            int nbx = bluePos.first, nby = bluePos.second;
            
            // 파란 구슬이 구멍에 빠지면 실패
            if (bHole) continue;
            
            // 빨간 구슬이 구멍에 빠지면 성공
            if (rHole) return cnt + 1;
            
            // 두 구슬이 같은 위치에 있으면 위치 조정
            if (nrx == nbx && nry == nby) {
                switch (dir) {
                    case 0: // 상
                        rx < bx ? nbx++ : nrx++;
                        break;
                    case 1: // 하
                        rx > bx ? nbx-- : nrx--;
                        break;
                    case 2: // 좌
                        ry < by ? nby++ : nry++;
                        break;
                    case 3: // 우
                        ry > by ? nby-- : nry--;
                        break;
                }
            }
            
            // 방문하지 않은 상태이면 큐에 추가
            if (!visited[nrx][nry][nbx][nby]) {
                visited[nrx][nry][nbx][nby] = true;
                q.push({nrx, nry, nbx, nby, cnt + 1});
            }
        }
    }
    
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M;
    
    int rx = 0, ry = 0, bx = 0, by = 0;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'R') {
                rx = i;
                ry = j;
            }
            else if (board[i][j] == 'B') {
                bx = i;
                by = j;
            }
        }
    }
    
    int result = bfs(rx, ry, bx, by);
    cout << result << '\n';
    
    return 0;
}