백준 17836 공주님을 구해라!

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

17836번: 공주님을 구해라!

#include <iostream>
#include <queue>

#define INF 987654321

using namespace std;


//0: 길, 1: 벽, 2: 칼
int map[101][101];

int cost[101][101];

bool isVisit[101][101];



int ny[4] = {-1, 1, 0, 0};
int nx[4] = {0, 0, -1, 1};


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, t;

    //칼의 위치
    pair<int, int> sword;

    int tCost;


    cin >> n >> m >> t;



    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) {
                sword = {i, j};
            }
            cost[i][j] = INF;
        }
    }

    queue<pair<int, int>> q;

    q.push({1, 1});
    cost[1][1] = 0;
    isVisit[1][1] = true;

    //bfs
    while (!q.empty()) {

        pair<int, int> cur = q.front();
        int cnt = cost[cur.first][cur.second];
        q.pop();

        //상하좌우 순으로 탐색
        for (int i = 0; i < 4; i++) {
            int newY = cur.first + ny[i];
            int newX = cur.second + nx[i];

            //지도를 벗어나는지? 해당 위치를 방문하지 않았는지?
            if (newY >= 1 && newY <= n && newX >= 1 && newX <= m && !isVisit[newY][newX]) {
                //해당 위치를 방문할 수 있는지?
                if (map[cur.first][cur.second] != 1) {
                    isVisit[newY][newX] = true;
                    q.push({newY, newX});
                    cost[newY][newX] = min(cost[newY][newX], cnt + 1);



                }
            }

        }

    }


    //검을 들 때부터 공주님께 가는 데 걸리는 시간
    int sToP = (n - sword.first) + (m - sword.second);


    tCost = min(cost[n][m], cost[sword.first][sword.second] + sToP);




    if (tCost <= t) {
        cout << tCost;
    } else {
        cout << "Fail";
    }



    return 0;
}

 

BFS 문제이다.

 

시작점에서 도착점까지 가는 방법은 두 가지가 있다.

 

1. 시작점부터 도착점까지 그냥 가는 경우

2. 칼을 잡고 길을 뚫어서 가는 경우

 

 

1번의 경우는 미로 찾기 문제이므로 bfs를 사용하면 된다.

2번의 경우는 bfs로 칼을 찾은 다음 도착점까지 가면 된다.

칼을 얻으면 무제한으로 사용할 수 있으므로 칼을 얻고 목적지까지 갈 때 걸리는 시간은

칼과 목적지까지를 직사각형으로 그렸을 때의 가로 길이+세로 길이이다.

 

1번의 경우와 2번의 경우 중 최솟값을 찾으면 최소 시간이다.

 

이 문제에 제한시간이 걸려있으므로 제한시간과 최소시간을 비교하여 조건에 맞게 답을 출력하면 된다.