[백준알고리즘] 13460번 구슬 탈출2

BOJ 13460번 :: 구슬 탈출2

문제 링크 : https://www.acmicpc.net/problem/13460

ㅎㅎ.. case문을 잘못 써서 이 부분에서 좀 오래 걸렸다..바보ㅠㅠ

구슬 탈출2 문제는 모든 경우를 다 해봐야 풀 수 있는 것이 아니라 최소 거리를 구하는 것이기 때문에 bfs를 통해 풀면 된다!

처음에 나는 그 방향으로 갈 수 있을 때까지 최대한 이동하는 것을..

for(현재 위치; 보드의 끝-1 까지; 그 방향으로 이동하면서)

위와 같이 짰었는데모든 경우마다 for문을 다 만들어줘야 해서 가시적이지 못하고 너무 지저분했다 ㅠㅠ

그래서 다른 사람들이 자주 사용하는 방법을 참고하여 while문으로 바꾸니 너무너무 코드가 보기 좋아지고 간편해졌다!

같은 위치일 때 좌표 갱신해 주는 것도 각자의 조건문을 만들어서 풀었을 때는 좋은 코드가 아니었는데

바꾼 것과 같이 switch문 안에 조건식을 넣으니 아주 편안해지는 코드가 되었다 ㅎ_ㅎ

나의 풀이

1) 각 구슬과 구멍의 위치를 저장한다.

2) 각 구슬이 방문했던 곳을 다시 방문하지 않기 위하여 4차원 visited배열을 만들어 각 구슬의 위치에 따른 방문 여부를 표시한다.

3) 빨간 구슬이 구멍에 들어가지 않는 동안 두 구슬을 bfs 방식으로 이동시키며 탐색한다.

3-1) 벽에 도달하지 않을 때까지 빨간 구슬과 파란 구슬을 4방향으로 이동시킨다, 구멍에 빠지면 break 한다.

3-2) 파란 구슬이 구멍에 빠졌으면 continue;

3-3) 같은 위치에 두 구슬이 겹쳐 있으면 이전 위치를 이용하여 구슬의 위치를 갱신한다.

3-4) 현재 위치에 두 구슬이 방문한 적이 있으면 continue; 방문한 적이 없으면 방문을 표시하고 탐색을 반복한다.

나의 코드

#include<iostream>
#include<string>
#include<queue>
using namespace std;
 
int N, M;
int rx, ry, bx, by; // 공의 위치
int hx, hy; // 구멍의 위치
bool flag;
int ans = 0; // 정답
char board[11][11]; // 보드
int visited[11][11][11][11]; // rx, ry, bx, by 위치에 따른 방문 여부 배열
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;
        }
    }
 
    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;
            redball.pop(); blueball.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];
 
                // 상하좌우 방향으로 구슬 움직이기
                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));
                visited[nrx][nry][nbx][nby] = true;
            }
        }
        if (flag) break;
        else ans++;
    }
 
    if (flag) cout << ans;
    else cout << -1;
 
    return 0;
}