[BOJ][백준]BFS-17836번 공주님을 구해라!

문제

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈를 반드시 하고 싶은 용사는 T시간 내에 반드시 공주님이 있는 곳으로 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸리며, 공주님이 있는 곳에 정확히 T초만에 도달하는 경우도, 구출 할 수 있다.

성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

입력

첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 5000)

두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

출력

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.

만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.

 

*******************************************************************************************************

평범한 BFS문제입니다. 기본 미로찾기문제에 "그람"이라는 변수만 잘 처리해주면되는데, queue<y,x,검을 획득했는지> 로 3차원으로 해결 할 수 있지만, 이보다 더 간단하게 해결할 수 있습니다.

공주에게 다다르기 까지는 2가지의 경우만 존재하는데, 첫째는 검을 획득하지않고 공주에게 가는 방법과,

둘째는 검을획득하고 다 통과를해서 공주에게 가는 방법입니다.

여기서 두번째 경우는 (용사와 검의 BFS거리+ 검과 공주의 거리)와 동일합니다. 또한 검과 공주의 거리는 

abs(검의y좌표-공주의y좌표)+abs(검의x좌표-공주의x좌표)를 뜻합니다. 벽을 통과할 수 있다면 BFS를 쓸 의미가 없으니 따로 증명을 하지 않아도 당연한 사실임을 알 수 있습니다. 이를 코드로 옮겨보면,

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;
const int INF=987654321;
int N,M,T,board[101][101];
const int goY[4]={0,0,1,-1};
const int goX[4]={1,-1,0,0};

bool is_in_board(int y,int x)
{
    if(y<1||y>N||x<1||x>M)return false;
    return true;
}

int BFS(int finY,int finX)
{
    int visited[101][101]={0,};
    queue<pair<int,int>>q;
    q.push({1,1});
    visited[1][1]=1;
    while(!q.empty())
    {
        int nowY=q.front().first,nowX=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nextY=nowY+goY[i],nextX=nowX+goX[i];
            if(is_in_board(nextY,nextX)&&!visited[nextY][nextX]&&board[nextY][nextX]!=1)
            {
                visited[nextY][nextX]=visited[nowY][nowX]+1;
                q.push({nextY,nextX});
            }
        }
    }
    return (visited[finY][finX]==0 ? INF:visited[finY][finX]-1);
}

int main()
{
    int swordY,swordX;
    cin>>N>>M>>T;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            cin>>board[i][j];
            if(board[i][j]==2)swordY=i,swordX=j;
        }
    int minTime=min(BFS(swordY,swordX)+abs(N-swordY)+abs(M-swordX),BFS(N,M));
    if(minTime<=T)cout<<minTime;
    else cout<<"Fail";
}

 도착점을 매개변수로 갖는 BFS함수를 만들어 간결하고 직관적이게 코드를 써내려갈 수 있습니다.

마지막 minTime을 구할때 abs(N-swordY)+abs(M-swordX) 는 N과M은 각각 swordY,X보다 큼이 보장되므로

절댓값(abs)을 생략해도 됩니다.