[13460] 구슬 탈출 2

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

오랜만에 구슬 탈출 문제를 풀어봤다.

몇 가지를 제외하고는 일반 bfs문제와 크게 다르지 않다.

1. 가져가는 주체가 빨간 구슬과 파란 구슬 두 개이다.

2. 한 번에 한 칸씩 움직이는 것이 아니라 갈 수 있는 곳 까지 움직인다.

3. 빨간 구슬만 목적지에 도착해야 한다.

이 것만 신경써주면 크게 어렵지 않은 문제이다. 다만 생각할게 많아서 귀찮을 뿐.

문제 푸는 원리는 이렇다.

큐에 빨간 구슬과 파란 구슬의 좌표를 가지고 간다.

무한 루프 방지를 위해 visit 배열을 사용하는데 여기도 마찬가지로 빨간 구슬과 파란 구슬의 좌표를 한번에 가진다.

그리고 각각 구슬을 서로 신경쓰지 않고 같은 방향으로 굴릴 수 있는 곳 까지 굴린다. 

굴릴 수 있는 곳은 다음 위치가 #이 아니고 현재 위치가  O가 아닌 곳이다.

굴리고 나서 처음 방문하는 곳이면 큐에 집어 넣는다.

그 위치가 O이면 끝.

이면 얼마나 좋을까.

일단 구슬을 서로 신경쓰지 않고 굴렸기 때문에 구슬들의 위치가 겹칠 경우가 발생한다.

이 때를 위해서 카운트 변수를 각 구슬마다 만들어

이동한 횟수를 비교해 더 많이 이동한 구슬(더 멀리서 온 구슬)은 이동한 방향대로 한 칸 뒤로 이동시켜준다.

다만 겹친 위치가 O일 경우에는 한 칸 뒤로 빼면 안된다. 두 구슬이 모두 빠질 수도 있기 때문이다.

그리고 함수의 기저사례중 파란 구슬이 먼저 O에 빠졌을 경우에는 continue를 이용해 

현재 큐에 남아있는 애들에게 기회를 더 주어야 한다.

상 하 좌 우로 움직였을 때 좌로 움직이면 파란 구슬이 빠지지만 우로 움직일 경우 빨간 구슬이 빠지는 경우가 있다고 가정하자.

이런 경우 좌의 좌표가 먼저 큐에 들어가 파란 구슬이 먼저 O에 도착했다고 -1를 출력하면 틀리게 된다.

마지막으로 10번의 횟수를 초과하면 -1를 출력해주는 코드만 추가해주면 된다.

끝.

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, rr, rc, br, bc;
char arr[12][12];
int visit[12][12][12][12];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
 
int bfs(){
    queue<pair<pair<int, int>, pair<int, int>> > qu;
    qu.push({{rr, rc},{br, bc}});
    int cnt = 0;
    while(int s = (int)qu.size()){
        while(s--){
            int crr, crc, cbr, cbc;
            crr = qu.front().first.first;
            crc = qu.front().first.second;
            cbr = qu.front().second.first;
            cbc = qu.front().second.second;
            qu.pop();
 
            if(visit[crr][crc][cbr][cbc]) continue;
            visit[crr][crc][cbr][cbc] = 1;
 
            if(arr[cbr][cbc] == 'O') continue;
 
            if(arr[crr][crc] == 'O')
                return cnt;
 
            for(int i=0; i<4; i++){
                int nrr, nrc, nbr, nbc, r, b;
                nrr = crr; nrc = crc; nbr = cbr; nbc = cbc;
                r = b = 0;
 
                while(arr[nrr + dx[i]][nrc + dy[i]] != '#' && arr[nrr][nrc] != 'O'){
                    nrr += dx[i];
                    nrc += dy[i];
                    r++;
                }
 
                while(arr[nbr + dx[i]][nbc + dy[i]] != '#' && arr[nbr][nbc] != 'O'){
                    nbr += dx[i];
                    nbc += dy[i];
                    b++;
                }
 
                if(nrr == nbr && nrc == nbc){
                    if(arr[nrr][nrc] == 'O') continue;
 
                    if(r<b){
                        nbr -= dx[i];
                        nbc -= dy[i];
                    }else{
                        nrr -= dx[i];
                        nrc -= dy[i];
                    }
                }
 
                if(!visit[nrr][nrc][nbr][nbc]){
                    qu.push({{nrr, nrc},{nbr, nbc}});
                }
            }
        }
        cnt++;
        if(cnt > 10) return -1;
    }
    return -1;
}
 
int main(){
    scanf("%d %d", &n, &m);
 
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf(" %1c", &arr[i][j]);
            if(arr[i][j] == 'R'){
                rr = i;    rc = j;
            }
            else if(arr[i][j] == 'B'){
                br = i;    bc = j;
            }
        }
    }
 
    printf("%d\n", bfs());
 
    return 0;
}