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

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

13460번: 구슬 탈출 2

우선 입력을 받고, 빨간 구슬의 위치와 파란 구슬의 위치를 구조체를 하나 만들어서 동시에 관리해준다.

큐에 담겨있는 정보를 가져와 4방향에 대해 탐색을 하는데, 벽을 만나거나 탐색한 곳이 구멍이 아닐 때까지 while문을 통해서 쭈욱 직진한다. (이 개념이 이해가 되지 않는다면 백준 레이저 통신 문제를 풀어보시길..!)

판을 한 방향으로 기울여 볼 때 마다 (for문이 한번 실행될 때 마다) 파란 구슬이 구멍을 만났다면 실패이므로 다른 방향에 대한 탐색을 진행해주고 (continue 이용), 빨간 구슬이 구멍을 만나면 그동안 판을 기울인 횟수를 출력하고 종료한다.

빨간 구슬과 파란 구슬이 겹치게 된다면, 멀리서 굴러온 구슬이 당연히 뒤에 있어야 한다..! rc, bc 변수를 계산하는 이유가 바로 이것 때문이다. 겹친다면 rc와 bc값을 비교해서 멀리서 굴러온 놈을 한칸 뒤로 물러주자

만약 이미 방문한 (판을 기울여본) 곳이라면 다음 탐색을 진행하고, 그렇지 않다면 방문 여부를 true로 바꿔주고 큐에 넣어서 해당 위치에서부터 새로운 탐색을 시작한다!

판을 기울인 횟수가 10번을 넘어가면 의미가 없으므로 break하고 -1을 출력한다!

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<cctype>
#include<cmath>

using namespace std;

struct state{
    int rx,ry;
    int bx,by;
    int d;
};
char map[10][10];
bool visited[10][10][10][10];
int n,m;
string str;
queue<state> q;

int dx[]={1,0,-1,0};
int dy[] = {0,1,0,-1};

void bfs(){
    while(!q.empty()) {
        int rx = q.front().rx;
        int ry = q.front().ry;
        int bx = q.front().bx;
        int by = q.front().by;
        int d = q.front().d;
        q.pop();

        if(d>=10) break;

        for (int i = 0; i < 4; i++) {
            int nrx = rx, nry = ry;
            int nbx = bx, nby = by;
            int rc=0, bc=0,nd = d+1;

            // 범위 안에 들고, 벽이 아닌 경우
            while (map[nrx+dx[i]][nry+dy[i]] != '#' && map[nrx][nry] != 'O') {
                nrx += dx[i];
                nry += dy[i];
                rc++;
            }
            while (map[nbx+dx[i]][nby+dy[i]] != '#' && map[nbx][nby] != 'O') {
                nbx += dx[i];
                nby += dy[i];
                bc++;
            }
            // 파란 구슬이 구멍에 빠지면 다른 방향 탐색
            if(map[nbx][nby]=='O') continue;

            if(map[nrx][nry]=='O') {
                cout << nd;
                return;
            }

            // 겹치면 더 뒤에서 출발한 구슬이 한칸 뒤로 무름
            if(nrx==nbx && nry == nby){
                if(rc > bc) nrx-= dx[i], nry -=dy[i];
                else nbx -= dx[i], nby -=dy[i];
            }
            if(visited[nrx][nry][nbx][nby]) continue;
            visited[nrx][nry][nbx][nby] = true;
            q.push({nrx,nry,nbx,nby,nd});
        }
    }
    cout << -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;

    int rx=0,ry=0,bx=0,by=0;

    for(int i=0; i<n; i++){
        cin >> str;
        for(int j=0; j<m;j++){
            map[i][j] = str[j];
            if(map[i][j] == 'R' ){
                rx = i;
                ry = j;
            }
            else if (map[i][j]=='B'){
                bx = i;
                by = j;
            }
        }
    }
    q.push({rx,ry,bx,by,0});
    visited[rx][ry][bx][by]=true;
    bfs();
}