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

💡 문제 설명

구슬 탈출 2

bfs 최단거리 문제이면서, 공이 두개라서 구현이 까다롭다.

💡 이동 함수

4 방향으로 이동했을때,

빨간공과 파란 공의 위치를 return해주는 함수를 만들었다.

항상 바깥쪽에는 벽이 있기 때문에 밖으로 떨어질 일은 없으니 벽과 만날때까지 이동시켜준다.

중간에 공이 구멍으로 들어가면 특별하게 처리해주기 위해서, 좌표를 음수로 표기해준다.

만약 파란 공과 빨간 공의 위치까지 생각해서 구현하려면 아주 복잡하고 길어지는데,

그렇게 하지 말고 무시하고 이동 한 후, 두 공의 좌표가 같다면 처리를 해주면 된다.

처리 방법
아래 상태에서 오른쪽으로 간다고 해보자.
R . . . B . . #
그냥 이동을 하면 R과 B가 같은 위치에 찍힐 것이다.
. . . . . . (RB) #
같은 위치라면, 방향에 따라서 뒤따라오던 애를 한칸 전으로 돌리면 된다.
. . . . . R B #

// 아래, 위, 오른, 왼
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

tuple<int,int,int,int> go(int dir, int rx, int ry, int bx, int by){

    int nrx=rx, nry=ry, nbx=bx, nby=by;
    // Red
    while(true){
        nrx+=dx[dir]; nry+=dy[dir];
        if (board[nrx][nry]=='#') {
            nrx-=dx[dir]; nry-=dy[dir];
            break;
        }
        // 구멍으로 빠짐 : -1로 표시
        if (board[nrx][nry]=='O'){
            nrx = -1; nry = -1;
            break;
        }
    } 
    // Blue
    while(true){
        nbx+=dx[dir]; nby+=dy[dir];
        if (board[nbx][nby]=='#') {
            nbx-=dx[dir]; nby-=dy[dir];
            break;
        }
        // 구멍으로 빠짐 : -2로 표시
        if (board[nbx][nby]=='O'){
            nbx = -2; nby = -2;
            break;
        }
    }
    // 두 좌표가 같다면 겹칠 수 없으므로 처리
    if(nrx==nbx && nry==nby){
        // 아래로 내려간거라면 위에있던걸 한단계 전으로
        if (dir==0){
            if (bx<rx) nbx -= dx[dir];
            else nrx -= dx[dir];
        }
        // 위로 올라간거라면 아래있던걸 한단계 전으로
        else if (dir==1){
            if (bx>rx) nbx -= dx[dir];
            else nrx -= dx[dir];
        }
        // 오른쪽으로 간거라면 왼쪽에 있던걸 한단계 전으로
        else if (dir==2){
            if (by<ry) nby -= dy[dir];
            else nry -= dy[dir];
        }
        // 왼쪽으로 간거라면 오른쪽에 있던걸 한단계 전으로
        else if (dir==3){
            if (by>ry) nby -= dy[dir];
            else nry -= dy[dir];
        }
    }

    return {nrx, nry, nbx, nby};
}

💡 BFS 최단거리

BFS 이기 때문에 dist가 낮은 것부터 처리된다.

10번 안에 도착하지 못하는 경우 바로 종료시켜주면 된다.

위 go 함수를 통해 B의 x좌표가 -2가 되었다면 빠진 것이므로, 더이상 진행하지 않고 다음 큐로 이동한다.

B는 안빠지면서 R의 x좌표가 -1이면 성공한것이므로 dist+1 을 리턴한다.

int bfs(int start_rx, int start_ry, int start_bx, int start_by){
    
    // Red 좌표, Blue좌표, 거리
    queue<tuple<int,int,int,int,int>> q;
    q.push({start_rx, start_ry, start_bx, start_by, 0});
    visited[start_rx][start_ry][start_bx][start_by]=true;
    
    while (!q.empty()){
        auto [rx, ry, bx, by, now_dist] = q.front();

        // 10번 안에 도착 못했을 경우
        // 10도 포함해야하는 이유 : 지금까지 온게 10이면,
        // 다음단계에 도달해도 return은 11이 되기 때문에
        if (now_dist>=10) {
            return -1;
        }

        q.pop();
        for (int i=0; i<4; i++){
            // 이동
            auto [nrx, nry, nbx, nby] = go(i, rx, ry, bx, by);

            // 파란색이 구멍에 빠짐
            if (nbx==-2) continue;

            // 파란색은 안빠지고 빨간색이 구멍에 빠지면 종료
            if (nrx==-1) return now_dist+1;

            if (visited[nrx][nry][nbx][nby]) continue;
            visited[nrx][nry][nbx][nby] = true;
            q.push({nrx, nry, nbx, nby, now_dist + 1});
        }
    }
    return -1;  // 도달 못했을 경우
}

💡 내 풀이

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii; typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const int INF = 0x7f7f7f7f;

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

상하좌우로 기울여서
R이 O로 들어가야함.
동시에 R, B 가 들어가면 안됨

#은 장애물, .은 빈공간
*/

#define MAX 10

int N, M;
char board[MAX][MAX];
bool visited[MAX][MAX][MAX][MAX];  // 빨간 구슬, 파란구슬

// 아래, 위, 오른, 왼
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

tuple<int,int,int,int> go(int dir, int rx, int ry, int bx, int by){

    int nrx=rx, nry=ry, nbx=bx, nby=by;
    // Red
    while(true){
        nrx+=dx[dir]; nry+=dy[dir];
        if (board[nrx][nry]=='#') {
            nrx-=dx[dir]; nry-=dy[dir];
            break;
        }
        // 구멍으로 빠짐 : -1로 표시
        if (board[nrx][nry]=='O'){
            nrx = -1; nry = -1;
            break;
        }
    } 
    // Blue
    while(true){
        nbx+=dx[dir]; nby+=dy[dir];
        if (board[nbx][nby]=='#') {
            nbx-=dx[dir]; nby-=dy[dir];
            break;
        }
        // 구멍으로 빠짐 : -2로 표시
        if (board[nbx][nby]=='O'){
            nbx = -2; nby = -2;
            break;
        }
    }
    // 두 좌표가 같다면 겹칠 수 없으므로 처리
    if(nrx==nbx && nry==nby){
        // 아래로 내려간거라면 위에있던걸 한단계 전으로
        if (dir==0){
            if (bx<rx) nbx -= dx[dir];
            else nrx -= dx[dir];
        }
        // 위로 올라간거라면 아래있던걸 한단계 전으로
        else if (dir==1){
            if (bx>rx) nbx -= dx[dir];
            else nrx -= dx[dir];
        }
        // 오른쪽으로 간거라면 왼쪽에 있던걸 한단계 전으로
        else if (dir==2){
            if (by<ry) nby -= dy[dir];
            else nry -= dy[dir];
        }
        // 왼쪽으로 간거라면 오른쪽에 있던걸 한단계 전으로
        else if (dir==3){
            if (by>ry) nby -= dy[dir];
            else nry -= dy[dir];
        }
    }

    return {nrx, nry, nbx, nby};
}

int bfs(int start_rx, int start_ry, int start_bx, int start_by){
    
    // Red 좌표, Blue좌표, 거리
    queue<tuple<int,int,int,int,int>> q;
    q.push({start_rx, start_ry, start_bx, start_by, 0});
    visited[start_rx][start_ry][start_bx][start_by]=true;
    
    while (!q.empty()){
        auto [rx, ry, bx, by, now_dist] = q.front();

        // 10번 안에 도착 못했을 경우
        // 10도 포함해야하는 이유 : 지금까지 온게 10이면,
        // 다음단계에 도달해도 return은 11이 되기 때문에
        if (now_dist>=10) {
            return -1;
        }

        q.pop();
        for (int i=0; i<4; i++){
            // 이동
            auto [nrx, nry, nbx, nby] = go(i, rx, ry, bx, by);

            // 파란색이 구멍에 빠짐
            if (nbx==-2) continue;

            // 파란색은 안빠지고 빨간색이 구멍에 빠지면 종료
            if (nrx==-1) return now_dist+1;

            if (visited[nrx][nry][nbx][nby]) continue;
            visited[nrx][nry][nbx][nby] = true;
            q.push({nrx, nry, nbx, nby, now_dist + 1});
        }
    }
    return -1;  // 도달 못했을 경우
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> N >> M;
    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            cin >> board[i][j];
        }
    }

    // 시작 지점 찾기
    int rx, ry, bx, by;
    for (int i=0; i<N; i++)
        for (int j=0; j<M; j++)
            if (board[i][j]=='R'){
                rx = i; ry = j; break;
            }
    for (int i=0; i<N; i++)
        for (int j=0; j<M; j++)
            if (board[i][j]=='B'){
                bx = i; by = j; break;
            }

    cout << bfs(rx, ry, bx, by);
    
    return 0;
}

💡 마무리

내가 풀고도 빨간 공과 파란 공이 만날때 처리를 잘 해준 것 같아서 만족했다.

이 코드를 조금만 수정해도 구슬 탈출 3, 구슬 탈출 4도 손쉽게 풀 수 있다.