[백준 17836번] 공주님을 구해라! (C++)

문제링크 : https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, M, T;
int dx[] = {1, -1, 0, 0};
int dy[] = {0 ,0, 1, -1};
int arr[100][100];
int cnt[100][100];
int check[100][100];

int bfs(int y, int x)
{
    queue<pii>q;
    q.push({y, x});
    check[y][x] = 1;
    int sword = MAX;

    while(!q.empty())
    {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();

        if(yy == N-1 && xx == M-1) // 목적지 도착
        {
            return min(sword, cnt[yy][xx]); 
        }

        if(arr[yy][xx] == 2)  //검 획득
        {
            sword = cnt[yy][xx] + ((N-1) - yy) + ((M-1) - xx); //검까지 거리 + 검부터 목적지까지 거리
        }

        for(int i=0; i<4; i++)
        {
            int nx = xx + dx[i];
            int ny = yy + dy[i];
            if(nx < 0 || nx >= M || ny < 0 || ny >=N) continue;
            if(arr[ny][nx] == 1) continue;
            if(check[ny][nx] == 1) continue;
            q.push({ny, nx});
            check[ny][nx] = 1;
            cnt[ny][nx] = cnt[yy][xx] + 1;
        }
    }
    if(sword != MAX) return sword;  //기존에 막혀있지만, 검을 얻어서 길이 생긴 경우
    else return -1;  //실패
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M >> T;

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cin >> arr[i][j];
        }
    }

    int result = bfs(0, 0);
    
    if(result == -1)
    {
        cout << "Fail";
    }
    else
    {
        if(result <= T) 
        {
            cout << result;
        }
        else 
        {
            cout << "Fail";
        }
    }

    return 0;
}

익숙한 bfs 문제에서 검에 대한 변수가 추가되었다.

검의 존재로 인해서 원래 탐색이 불가능하나, 탐색이 가능한 경우가 생긴다.

따라서 검에 도착했을 때 검까지 카운트한 거리와 검에서 목적지까지의 거리를 저장해두고 이를 활용한다.

검에서 목적지까지의 거리는 좌표계산으로 바로 계산할 수 있다.