[Baekjoon,13460]구슬 탈출 2

해결

최단거리를 구해야 하므로 너비 우선 탐색을 통해 접근했다. 하지만 일반적인 BFS와는 다르게 다음 상태 정점에 접근하기 어려웠고, 중간에 탈출하게 되었을 때의 처리의 구현이 어려웠다.

일단 이동하고 판단하자

다음 상태 구슬의 위치를 계산하기 위해서 제일 무난한 방법은 먼저 한칸 옮기고 나서 이동 가능한지 판단하는 것이다. 벽을 만나거나 구멍에 빠지거나 등을 고려해야 했다. 어떤 경우에서도 파란 구슬은 구멍에 빠지면 안되므로 이 경우를 만나면 바로 건너 뛰었다. 두 구슬이 겹쳐진 경우도 생각해야 한다. 이때는 먼저 벽에 다다른 구슬이 아닌 다른 구슬을 이전 위치로 한 칸 옮기면 해결된다. 그 후 구슬의 위치를 계산했는데 이전에 이미 위치했던 곳이면 진행하지 않는다.

최소 횟수를 어떻게 계산하지?

하나의 방법은 큐에 움직인 횟수를 포함시켜 계산하는 것이다. 하지만 나는 다른 방법을 선택했다. 바로 그래프의 깊이가 같은 정점의 개수만큼 반복하는 것이다. 1단계 깊이에 3개의 상태가 추가되면 세 번을 2단계 깊이의 다음 상태를 찾으며 추가하고, 이때 2단계 깊이에 9개가 추가되면 아홉 번 반복하는 것이다.

제한 걸기

기울이기가 10번이 넘어가면 의미가 없으므로 이때는 -1을 반환하도록 한다.

구현

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int,int> pii;

enum { RED=0, BLUE };

const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};

int H,W;
// 각 구슬의 y,x 좌표 위치 
pii red,blue,hole;
vector<string> board;
bool discoverd[10][10][10][10];

int bfs()
{
    // <red, blue>
    queue<pair<pii,pii> > q;
    q.push(make_pair(red,blue));
    discoverd[red.first][red.second][blue.first][blue.second]=true;
    int moveCount=0;
    bool escape=false;
    // 시작점에서 단계마다 반복한다.
    while(!q.empty())
    {
        int levelCount=q.size();
        while(levelCount--)
        {
            // [0]=red, [1]=blue
            pii here[2]={ q.front().first, q.front().second };
            q.pop();
            // 빨간 공이 빠져 나간 경우
            if(board[here[RED].first][here[RED].second]=='O')
            {
                escape=true;
                break;
            }
            // 기울여서 다음 위치를 찾는다.
            for(int dir=0;dir<4;++dir)
            {
                pii there[2]={ here[RED], here[BLUE] };
                int count[2]={0,};
                bool isGoal[2]={false,false};
                // 빨간 구슬 이동 후 파란 구슬 이동
                for(int color=0;color<2;++color)
                {
                    int& ny=there[color].first;
                    int& nx=there[color].second;
                    // 벽을 접할 때까지 이동
                    while(board[ny+dy[dir]][nx+dx[dir]]!='#')
                    {
                        ++count[color];
                        ny+=dy[dir];
                        nx+=dx[dir];
                        // 구르는 중 구멍에 빠진 경우
                        if(there[color]==hole)
                            break;
                    }
                    // 구멍에 빠졌는 지 확인
                    isGoal[color]=(there[color]==hole);
                }
                
                // 어떤 경우에도 파란 구슬이 빠지면 안된다.
                if(isGoal[BLUE])
                    continue;
                
                // 두 공이 겹쳐진 경우 늦게 벽에 다다른 공을 뒤로 뺀다.
                if(there[RED].first==there[BLUE].first && 
                   there[RED].second==there[BLUE].second)
                {
                    if(count[RED]>count[BLUE])
                    {
                        there[RED].first-=dy[dir];
                        there[RED].second-=dx[dir];
                    }
                    else
                    {
                        there[BLUE].first-=dy[dir];
                        there[BLUE].second-=dx[dir];
                    }
                }
                // 이미 만들어졌던 위치는 제외한다.
                if(!discoverd[there[RED].first][there[RED].second][there[BLUE].first][there[BLUE].second])
                {
                    discoverd[there[RED].first][there[RED].second][there[BLUE].first][there[BLUE].second]=true;
                    q.push(make_pair(there[RED],there[BLUE]));
                }
            }
        }
        // 현재 단계에서 탈출한 경우
        if(escape) break;
        
        ++moveCount;
        // 10번 이상의 기울이기는 무의미하다
        if(moveCount>10) break;
    }
    return escape ? moveCount : -1;
}

int main()
{
    cin>>H>>W;
    board.resize(H);
    for(int i=0;i<H;++i)
        cin>>board[i];
    
    for(int y=0;y<H;++y)
        for(int x=0;x<W;++x)
        {
            char box=board[y][x];
            switch(box)
            {
            case 'R': red=make_pair(y,x); break;
            case 'B': blue=make_pair(y,x); break;
            case 'O': hole=make_pair(y,x); 
            }
        }
    
    cout<<bfs()<<endl;
    
    return 0;
}

참고

비락 식혜를 낳는 블로그-백준 13460 구슬 탈출 2