[C++]백준 6146번 신아를 만나러

📌문제 링크

---

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

📌문제 설명

---

좌표가 -500부터 500까지 가능하므로 각 좌표의 입력을 +500씩 처리하여 기본 bfs 최단거리 탐색을 하면 된다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
bool mp[1001][1001];
int X, Y, N, dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

struct comp{
    int x, y, cnt;
};

void input(){
    cin >> X >> Y >> N;
    for(int i = 0; i < N; i++){
        int a, b;
        cin >> a >> b;
        mp[a + 500][b + 500] = true;
    }
}

void bfs(){
    queue<comp> q;
    q.push({500, 500, 0});
    mp[500][500] = true;
    while(!q.empty()){
        auto [x, y, cnt] = q.front();
        q.pop();
        if(x == X + 500 && y == Y + 500){
            cout << cnt;
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(mp[nx][ny]){
                continue;
            }
            mp[nx][ny] = true;
            q.push({nx, ny, cnt + 1});
        }
    }
}

void solve(){
    input();
    bfs();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}