[BaekJoon] 13459 구슬 탈출, 13460 구슬 탈출2 :: monton

문제

13459 구슬 탈출 https://www.acmicpc.net/problem/13459

13460 구슬 탈출2 https://www.acmicpc.net/problem/13460

풀이

최소 움직인 횟수를 구하는 문제이므로 bfs 사용

R구슬이 움직일때 B구슬의 위치도 중요하므로 visit[MAX R구슬][MAX R구슬][MAX B구슬][MAX B구슬] 이용

bfs로 상하좌우를 탐색하며 갈 수 있는 곳을 큐에 넣어준다

여기서 중요한 점은 R구슬과 B구슬이 같은 위치에 놓일때 예외 처리가 중요한데

if문을 사용하여 아래 코드와 같이 처리해주면 된다

13460 구슬 탈출2 문제는 움직이는 횟수를 구하는 문제 이므로

주어진 코드를 ans를 출력하는 방법으로 바꾸어 주면 된다.

코드

13459 구슬 탈출, 13460 구슬 탈출2

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, M,ans;
char arr[11][11];
int visit[11][11][11][11];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
queue<int> rx,ry,bx,by;
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'R') rx.push(i), ry.push(j);
            if (arr[i][j] == 'B') bx.push(i), by.push(j);
        }
    }
    visit[rx.front()][ry.front()][bx.front()][by.front()] = 1;
    
    while (!rx.empty()) {
        
        int qsize = rx.size();
        while (qsize--) {
            int nrx = rx.front();
            int nry = ry.front();
            int nbx = bx.front();
            int nby = by.front();
 
            rx.pop(), ry.pop(), bx.pop(), by.pop();
 
            if (arr[nrx][nry]== 'O') {
                cout << '1'<<endl;
                return 0;
            }
 
            for (int i = 0; i < 4; i++) {
                int nnrx = nrx;
                int nnry = nry;
                int nnbx = nbx;
                int nnby = nby;
                int flag = 0;
 
                while (arr[nnrx + dir[i][0]][nnry + dir[i][1]] != '#'&&arr[nnrx][nnry] != 'O') {
                    nnrx += dir[i][0];
                    nnry += dir[i][1];
                }
 
                while (arr[nnbx + dir[i][0]][nnby + dir[i][1]] != '#'&&arr[nnbx][nnby] != 'O') {
                    
                    nnbx += dir[i][0];
                    nnby += dir[i][1];
 
                    if (arr[nnbx][nnby] == 'O') flag = 1;
                }
 
                if (nnrx == nnbx&&nnry == nnby) {
                    if (i == 0) {
                        if (nrx > nbx) nnrx += 1;
                        else nnbx += 1;
                    }
                    else if (i == 1) {
                        if (nry > nby) nnby -= 1;
                        else nnry -= 1;
                    }
                    else if (i == 2) {
                        if (nrx > nbx) nnbx -= 1;
                        else nnrx -= 1;
                    }
 
                    else if (i == 3) {
                        if (nry > nby) nnry += 1;
                        else nnby += 1;
                    }
                }
 
                if (flag) continue;
                if (visit[nnrx][nnry][nnbx][nnby]) continue;
                visit[nnrx][nnry][nnbx][nnby] = 1;
                rx.push(nnrx), ry.push(nnry), bx.push(nnbx), by.push(nnby);
            }
        }
        ans++;
        if (ans > 10) break;
    }
    cout << '0' << endl;
}