[백준 13460] 구슬탈출 2

안녕하세요 !!! 우디😎입니다.

오늘은 BFS로 푼 구슬 탈출 2 문제에 대해 설명해드릴께요.

 

문제

[백준 13460] 구슬탈출 2 바로가기

 

문제 설명

< 이 문제의 KEY POINT >

• 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다. ==> 10번 동안의 BFS

• 파란 구슬이 구멍에 들어가면 실패 , 기울이는 동작은 구슬의 움직임이 없을 때까지 기울임. (백준 예제 7번) ==> (빨간 구슬과 파란 구슬이 동시에 들어갈 수 있음)

 

😘 : 위의 KEY POINT 대로 차근차근 설명해드리겠습니다.

 

➊. 10번 동안의 BFS

빨간 구슬이 구멍을 찾아가기 위해서 상,하,좌,우 중 10개의 방향을 조합해서 찾을 수가 있습니다.

또한, 최적화 하여 한방에 ! 빨간 구슬이 구멍을 찾아갈 수 있을 까요 ??? 불가능 합니다.

따라서, 이 문제는 완전 탐색이 되겠습니다 !

구현 방법으로는 BFS가 적합한데 이유는 트리를 통해 설명해 드리겠습니다.

🌳 트리

위의 그림처럼 처음 시작을 상 하 좌 우 로 한 트리가 4가지가 나올 수 있습니다.

맨 왼쪽 상 방향을 시작으로 한 트리를 보자면 구슬이 상으로 움직인 다음 좌, 우로 움직인다고 되어있습니다.

여기서, 상으로 움직인 다음 상,하,좌,우로 움직일 수도 있지 않느냐 하실 수 있는데, 문제에서의 답은 구슬은 최소로 움직여야 합니다.

 

🎨따라서, 상으로 움직였는데 다시 상으로 움직일 필요는 없겠죠 ~

🎨또한, 하로 다시 움직여 버린다면 구슬이 제자리 걸음만 되는 격이니, 필요가 없습니다 ~

 

이처럼, 상으로 움직인 것을 좌, 우로 움직일 수 있고, 좌로 움직인 것은 다시 상,하 우로 움직인 것은 다시 상,하로 움직이는 등 트리에서 넓게 넓게 가로로 가로로(?) 탐색해주죠 ??

그래서, BFS로 풀면 됩니다 !!!

 

➋. 구슬의 이동

구슬의 이동

1. 구슬 2개가 나란히 있을때, 먼저 이동시켜줘야 하는 구슬 생각하기
2. 빨간 구슬이 구멍에 빠지고 안빠지는 동시에 파란 구슬이 빠지고 안빠지는 경우 (총 4가지)

✍ 휴도 코드

x
int RED(방향)//빨간 공 먼저 이동시켜줘야 하는 경우
{
    int red_ox = 0;
    int blue_ox = 0;//빠짐 : 1 / 안빠짐 : 0 표식
​
    int rx = RED큐 x좌표
    int ry = RED큐 y좌표
        
    while (1)
    {
        //빨간 공 한칸씩 이동함.
        if //구멍에 빠짐
        {
            red_ox = 1;//빨강 구멍 빠짐
            //빨간 공 한칸 더 이동 (빨간공 끝까지 이동해서 좌표에 없애서 파란공 구멍에 빠지는지 봄)
        }
        if //벽이거나 파란구슬 만나면
        {
            break;
        }
    }//빨강 먼저 옮김
​
    int new_rx = rx - dx[direction];
    int new_ry = ry - dy[direction];//빨간공 좌표가 바꼈으니 갱신
​
    int bx = BLUE큐 x좌표
    int by = BLUE큐 y좌표
    
    while (1)
    {
        //파란 공 한칸씩 이동함.
        if //구멍에 빠짐
        {
            blue_ox = 1;//파란 구멍 빠짐
            //파란 공 이동
        }
        if //벽이거나 빨강구슬 만나면
        {
            break;
        }
    }
    //   빨강   |    파랑     O:구멍에 빠짐  X:안빠짐
    //    O     |    O       : 실패 -1
    //    O     |    X       : 성공
    //    X     |    O       : 실패 -1
    //    X     |    X       : 계속 이동하세요 ~
 
    if (blue_ox == 1) return -1;//파란 구슬 구멍에 빠짐
    else if (red_ox == 0 && blue_ox == 0)//빨간 파란 둘 다 안빠짐 --> 다음 방향 dir큐에 넣어줌.
    {
        R.push(make_pair(rx - dx[direction], ry - dy[direction]));
        B.push(make_pair(bx - dx[direction], by - dy[direction]));
        return 0;//빨강 파랑 둘 다 이동됨.
    }
    else if (red_ox == 1 && blue_ox == 0) return cnt;//빨간 구슬만 구멍에 빠짐. 답 저장
}

 

구현

x
#include <iostream>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <queue>
using namespace std;
​
int arr[12][12];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int cnt = 0;
​
queue<int>dir;
queue<pair<int, int>>R;
queue<pair<int, int>>B;
​
int bfs();
int red(int direction);
int blue(int direction);
​
int main()
{
    static int n, m;
    cin >> n >> m;
​
    static int rrx;
    static int rry;
    static int rbx;
    static int rby;
​
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++)
        {
            string s = str.substr(j, 1);
            if (s.compare("#") == 0) arr[i][j] = -1;
            else if (s.compare("O") == 0) arr[i][j] = 1;//구멍
            else if (s.compare(".") == 0) arr[i][j] = 0;
            else if (s.compare("R") == 0)
            {
                R.push(make_pair(i, j));//RED 좌표
                rrx = i;
                rry = j;
                arr[i][j] = 44;
            }
            else if (s.compare("B") == 0)
            {
                B.push(make_pair(i, j));//BLUE 좌표
                rbx = i;
                rby = j;
                arr[i][j] = 66;
            }
        }
    }
​
    priority_queue<int, vector<int>, greater<int> > answer;
​
    int ans = 0;
    for (int i = 0; i < 4; i++)
    {
        dir.push(i);
        ans = bfs();
        if (ans != -1)answer.push(ans);
        while (!dir.empty())
            dir.pop();
        while (!R.empty())
            R.pop();
        while (!B.empty())
            B.pop();
        R.push(make_pair(rrx, rry));
        B.push(make_pair(rbx, rby));
    }
    if (!answer.empty())
        cout << answer.top();//정답
    else
        cout << -1 << endl;
    
}
​
int bfs()
{
    for (cnt = 1; cnt < 11; cnt++)
    {
        int num = dir.size();
        for (int a = 1; a <= num; a++)
        {
            int d = dir.front();
            dir.pop();
            if (d == 0)//상
            {
                if (R.front().first < B.front().first)//red 먼저 이동
                {
                    int a = red(d);
                    if (a == 0)//red blue 둘다 이동
                    {
                        dir.push(2);
                        dir.push(3);
                    }//좌우 넣어줌
                    else if (a > 0)
                        return cnt;//bfs 함수 종료
                }
                else
                {
                    int b = blue(d);
                    if (b == 0)//red blue 둘다 이동
                    {
                        dir.push(2);
                        dir.push(3);
                    }//좌우 넣어줌
                    else if (b > 0)
                        return cnt;
                }
            }//상
            if (d == 1)//하
            {
            
                if (R.front().first > B.front().first)//red 먼저 이동
                {
                    int a = red(d);
                    if (a == 0)//red blue 둘다 이동
                    {
                        dir.push(2);
                        dir.push(3);
                    }//좌우 넣어줌
                    else if (a > 0)
                        return cnt;
                }
                else
                {
                    int b = blue(d);
                    if (b == 0)//red blue 둘다 이동
                    {
                        dir.push(2);
                        dir.push(3);
                    }//좌우 넣어줌
                    else if (b > 0)
                        return cnt;
                }
            }//하
            if (d == 2)//좌
            {
                if (R.front().second < B.front().second)//red 먼저 이동
                {
                    int a = red(d);
                    if (a == 0)//red blue 둘다 이동
                    {
                        dir.push(0);
                        dir.push(1);
                    }//좌우 넣어줌
                    else if (a > 0)
                        return cnt;
                }
                else
                {
                    int b = blue(d);
                    if (b == 0)//red blue 둘다 이동
                    {
                        dir.push(0);
                        dir.push(1);
                    }//좌우 넣어줌
                    else if (b > 0)
                        return cnt;
                }
            }//좌
            if (d == 3)//우
            {
                if (R.front().second > B.front().second)//red 먼저 이동
                {
                    int a = red(d);
                    if (a == 0)//red blue 둘다 이동
                    {
                        dir.push(0);
                        dir.push(1);
                    }//좌우 넣어줌
                    else if (a > 0)
                        return cnt;
                }
                else
                {
                    int b = blue(d);
                    if (b == 0)//red blue 둘다 이동
                    {
                        dir.push(0);
                        dir.push(1);
                    }//좌우 넣어줌
                    else if (b > 0)
                        return cnt;
                }
            }//우
            if (a%2==0 || num == 1)
            {
                R.pop();
                B.pop();
            }//한 방향당 2개의 방향을 추가시키기 때문에 2개씩 끊어서 pop해줌(dir크기 1이면 무조건 pop)
        }//dir.size만큼 도는 것
    }
    return -1;
}
​
int red(int direction)//주의 : 
{
    int red_ox = 0;
    int blue_ox = 0;//빠짐 : 1 / 안빠짐 : 0 표식
​
    int rx = R.front().first;
    int ry = R.front().second;
    
    while (1)
    {
        rx += dx[direction];
        ry += dy[direction];
        if (arr[rx][ry] == 1)
        {
            red_ox = 1;//빨강 구멍 빠짐
            rx += dx[direction];
            ry += dy[direction];// 더 가 !
        }
        if (rx == B.front().first && ry == B.front().second || arr[rx][ry] == -1)//벽이거나 파란구슬 만나면
        {
            break;
        }
    }//빨강 먼저 옮김
​
    int new_rx = rx - dx[direction];
    int new_ry = ry - dy[direction];
​
    int bx = B.front().first;
    int by = B.front().second;
    
    while (1)
    {
        bx += dx[direction];
        by += dy[direction];
        if (arr[bx][by] == 1)
        {
            blue_ox = 1;//파랑 구멍 빠짐 실패 -1
            bx += dx[direction];
            by += dy[direction];
        }
        if (bx == new_rx && by == new_ry|| arr[bx][by] == -1)//벽이거나 빨간구슬 만나면
        {
            break;
        }
    }
    if (blue_ox == 1) return -1;
    else if (red_ox == 0 && blue_ox == 0)
    {
        R.push(make_pair(rx - dx[direction], ry - dy[direction]));
        B.push(make_pair(bx - dx[direction], by - dy[direction]));
        return 0;//빨강 파랑 둘 다 이동됨.
    }
    else if (red_ox == 1 && blue_ox == 0) return cnt;
}
​
int blue(int direction)
{
    int red_ox = 0;
    int blue_ox = 0;//빠짐 : 1 / 안빠짐 : 0 표식
​
    int bx = B.front().first;
    int by = B.front().second;
​
    while (1)
    {
        bx += dx[direction];
        by += dy[direction];
        if (arr[bx][by] == 1)
        {
            blue_ox = 1;//파랑 구멍 빠짐 실패 -1
            bx += dx[direction];
            by += dy[direction];
        }
        if (bx == R.front().first && by == R.front().second || arr[bx][by] == -1)//벽이거나 빨간구슬 만나면
        {
            break;
        }
    }
​
    int new_bx = bx - dx[direction];
    int new_by = by - dy[direction];
    int rx = R.front().first;
    int ry = R.front().second;
​
    while (1)
    {
        rx += dx[direction];
        ry += dy[direction];
        //cout << rx << ry << endl;
        if (arr[rx][ry] == 1)
        {
            red_ox = 1;//빨강 구멍 빠짐
            rx += dx[direction];
            ry += dy[direction];
        }
        if (rx == new_bx && ry == new_by || arr[rx][ry] == -1)//벽이거나 파란구슬 만나면
        {
            break;
        }
    }//빨강 먼저 옮김
​
    
    if (blue_ox == 1) return -1;
    else if (red_ox == 0 && blue_ox == 0)
    {
        B.push(make_pair(bx - dx[direction], by - dy[direction]));
        R.push(make_pair(rx - dx[direction], ry - dy[direction]));
        return 0;//빨강 파랑 둘 다 이동됨.
    }
    else if (red_ox == 1 && blue_ox == 0) return cnt;
}