BOJ - 공주님을 구해라! (17836)

https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

 

 

딱 두가지 경우만 생각해보면 된다.

 

1. 전설의 명검없이 바로 공주가 있는 곳으로 간다.

2. 전설의 명검이 있는 곳으로 간 후, 공주가 있는 곳으로 간다.

 

두 가지 중 적은 시간을 출력한다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
struct ss {
    int y, x;
};
 
int n, m;
 
bool range(int y, int x) {
    return !(y < 0 || y >= n || x < 0 || x >= m);
}
 
int mp[111][111];
int t;
                                // 전형적인 bfs 코드이므로 설명은 생략
int bfs(int y, int x) {            // 도착지 (y, x)까지 bfs를 통해 최단거리를 구하는 함수
    bool chk[111][111] = {};
    queue<ss> q;
    
    q.push({ 0,0 });
    chk[0][0] = true;
 
    int step = 0;
 
    bool ff = false;
    while (!q.empty()) {
        int l = q.size();
        while (l--) {
            ss f = q.front();
            q.pop();
 
            if (f.y == y && f.x == x) {
                ff = true; 
                break;
            }
 
            for (int dir = 0; dir < 4; dir++) {
                int ny = f.y + dy[dir], nx = f.x + dx[dir];
                if (!range(ny, nx) || chk[ny][nx] || mp[ny][nx] == 1) continue;
                chk[ny][nx] = true;
                q.push({ ny, nx });
            }
        }
        if (ff) break;
        step += 1;
    }
 
    if(ff) return step;
    else return 123456789;
}
 
 
int main() {
    cin >> n >> m >> t;
    
    ss sword;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == 2) {
                sword = { i, j };
                mp[i][j] = 0;
            }
        }
 
    int a = bfs(n - 1 , m - 1);                                            // 전설의 명검 없이 바로 공주가 있는 곳으로 가는 경우
    int b = bfs(sword.y, sword.x) + n - 1 - sword.y + m - 1 - sword.x;    // 전설의 명검이 있는 곳으로 간 후, 공주가 있는 곳으로 가는 
 
    if (a > t && b > t) {
        cout << "Fail";
    }
    else {
        cout << min(a, b);
    }
}