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

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

17836번: 공주님을 구해라!

최단거리를 찾는 BFS 문제이다.

2차원 배열에서 방문하지 않은 점을 방문하면서 탐색하면 되고, 탐색도중 그람이 있으면 그 위치부터 맨해튼 거리값을 더해서 최소 값이 되는지 확인하면 된다.

 

 

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int map[100][100] = { 0 };
int N, M, T;
int d[8] = { -1,0,0,1,1,0,0,-1 };
int bfs(pair<int,int>start, pair<int,int> end, pair<int,int> gram) {
    int visit[100][100] = { 0 };
    int i, j, r, c, dr,dc, nr,nc, dist, ret, tmp;
    queue<pair<int, pair<int,int>>> q;
    
    q.push(make_pair(0, start));
    ret = 100000;
    visit[start.first][start.second] = 0; // 1더했으니 뒤에서 1빼야됨
    while (!q.empty()) {
        dist = q.front().first;
        r = q.front().second.first;
        c = q.front().second.second;
        q.pop();
        if (dist > ret) break;
        if (end.first == r && end.second == c) {
            ret = min(dist, ret);
            break;
        }
        if (gram.first == r && gram.second == c) {
            tmp = dist + abs(gram.first - N + 1) + abs(gram.second - M + 1);
            ret = min(tmp, ret);
        } 
        for (i = 0; i < 4; i++)
        {
            dr = r + d[2 * i];
            dc = c + d[2 * i + 1];
            if (dr < 0 || dr >= N || dc < 0 || dc >= M) continue;
            if (map[dr][dc] == 1) continue;
            if (visit[dr][dc]) continue;
            visit[dr][dc] = dist + 1;
            q.push(make_pair(dist + 1, make_pair(dr, dc)));
        }
    }
    if (ret > T)
        return -1;
    return ret;
}
int main() {
    // 0 init
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int i, j, ans;
    pair<int, int> gram;
    // 1 input
    cin >> N >> M >> T;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 2)
                gram = make_pair(i, j);
        }
    }
    
    ans = bfs(make_pair(0, 0), make_pair(N-1,M-1), gram);
    if (ans == -1) {
        cout << "Fail";
    }
    else {
        cout << ans;
    }
    cout << "\n";
    

    return 0;
}