Lv. 3 나무 섭지 - C++

#include <iostream>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int n, m;
pair<int, int> s;
vector<pair<int, int>> g;
char maze[1001][1001];
bool visited[1001][1001];

int get_ghost_min_dist(int h, int w, vector<pair<int, int>>& ghost) {
    int dist = 2001;
    for (auto& g : ghost) {
        dist = min(dist, abs(h - g.first) + abs(w - g.second));
    }
    return dist;
}

bool bfs(pair<int, int> start, vector<pair<int, int>>& ghost) {
    queue<pair<pair<int, int>, int>> q;  // ((y, x), depth)
    q.push({start, 0});
    visited[start.first][start.second] = true;

    while (!q.empty()) {
        auto [pos, d] = q.front();
        int h = pos.first, w = pos.second;
        q.pop();

        if (maze[h][w] == 'D') {
            cout << "Yes" << endl;
            return true;
        }

        if (d >= get_ghost_min_dist(h, w, ghost)) {
            visited[h][w] = true;
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int next_y = h + dy[i];
            int next_x = w + dx[i];
            if (next_y >= 0 && next_y < n && next_x >= 0 && next_x < m && !visited[next_y][next_x] && maze[next_y][next_x] != '#') {
                visited[next_y][next_x] = true;
                q.push({{next_y, next_x}, d + 1});
            }
        }
    }

    return false;
}

int main(int argc, char** argv) {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
            visited[i][j] = false;
            if (maze[i][j] == 'N') {
                s = {i, j};
            }
            else if (maze[i][j] == 'G') {
                g.push_back({i, j});
            }
        }
    }

    if (!bfs(s, g)) {
        cout << "No" << endl;
    }

    return 0;
}

핵심은 bfs 돌면서
1. '지금 위치에서 유령들과의 거리의 최소값'
2. '시작위치에서 지금 위치까지의 거리'
를 비교해서 1이 더 작거나 같으면, 유령이 우리 남우씨를 잡게되니까 그 위치는 탐색중단합니다