[백준알고리즘] 15644번 구슬 탈출3

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

구슬 탈출2 에서 공이 이동한 방향의 집합인 string을 저장하는 queue를 추가하여 풀었다!

직전까지의 이동한 방향에서 현재 이동한 방향을 추가하여 balldirect 라는 이름의 queue에 넣고 빼는 식으로 구현한다!

<나의 코드>

#include<iostream>
#include<string>
#include<queue>
using namespace std;
 
int N, M;
int rx, ry, bx, by; // 공의 위치
string cur_ball_dir; // 지금까지의 공이 이동한 방향
char bd[4] = {'U', 'D', 'L', 'R'};
int hx, hy; // 구멍의 위치
bool flag;
int ans = 0; // 탐색 횟수
char board[11][11]; // 보드
int visited[11][11][11][11]; // rx, ry, bx, by 위치에 따른 방문 여부 배열
queue<string> balldirect; // 공의 이동방향
queue<pair<int, int>> redball; // 빨간 공 위치
queue<pair<int, int>> blueball; // 파란 공 위치
 
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
 
int main(void)
{
    string str;
    cin >> N >> M;
 
    for (int i = 0; i < N; i++)
    {
        cin >> str;
        for (int j = 0; j < M; j++)
        {
            board[i][j] = str[j];
            if (board[i][j] == 'R') {
                redball.push(make_pair(i, j)); rx = i, ry = j;
            }
            if (board[i][j] == 'B') {
                blueball.push(make_pair(i, j)); bx = i, by = j;
            }
            if (board[i][j] == 'O') hx = i, hy = j;
        }
    }
    balldirect.push("");
 
    visited[rx][ry][bx][by] = true;
 
    while (!redball.empty())
    {
        int qsize = redball.size();
 
        while (qsize--)
        {
            rx = redball.front().first;
            ry = redball.front().second;
            bx = blueball.front().first;
            by = blueball.front().second;
            cur_ball_dir = balldirect.front();
            redball.pop(); blueball.pop(); balldirect.pop();
 
            // 10번 이상 탐색했으면 break
            if (ans > 10) break;
            // 빨간 구슬이 구멍에 빠지면 break
            if (rx == hx && ry == hy) { flag = true; break;}
 
            for (int i = 0; i < 4; i++)
            {
                int nrx = rx + dx[i];
                int nry = ry + dy[i];
                int nbx = bx + dx[i];
                int nby = by + dy[i];
                string ncur_ball_dir = cur_ball_dir;
 
                // 상하좌우 방향으로 구슬 움직이기
                while (1)
                {
                    if (board[nrx][nry] == '#') {
                        nrx -= dx[i]; nry -= dy[i];
                        break;
                    }
                    if (board[nrx][nry] == 'O') break;
                    nrx += dx[i]; nry += dy[i];
                }
                while (1)
                {
                    if (board[nbx][nby] == '#') {
                        nbx -= dx[i]; nby -= dy[i];
                        break;
                    }
                    if (board[nbx][nby] == 'O') break;
                    nbx += dx[i]; nby += dy[i];
                }
 
                // 파란 구슬이 구멍에 빠지면 continue
                if (nbx == hx && nby == hy) continue;
 
                // 같은 위치에 두 개의 구슬이 있으면 위치 갱신
                if (nrx == nbx && nry == nby)
                {
                    switch (i){
                    case 0: rx > bx ? nrx++ : nbx++; break;
                    case 1: rx < bx ? nrx-- : nbx--; break;
                    case 2: ry > by ? nry++ : nby++; break;
                    case 3: ry < by ? nry-- : nby--; break;
                    }
                }
                
                // 방문했던 지점이 아니면 push
                if (visited[nrx][nry][nbx][nby]) continue;
                redball.push(make_pair(nrx, nry));
                blueball.push(make_pair(nbx, nby));
                ncur_ball_dir.push_back(bd[i]); // 다음 방향 추가하기
                balldirect.push(ncur_ball_dir); // 다음 방향 추가된 문자열 저장하기
                visited[nrx][nry][nbx][nby] = true;
            }
        }
        if (flag) break;
        else ans++;
    }
 
    if (flag)
    {
        cout << ans << '\n' << cur_ball_dir;
    }
    else cout << -1;
 
    return 0;
}