[BOJ] 1909 냄새 싫어

출처 : 카톡 이모티콘 김춘배

일단 이 문제가 왜 다4인지 모르겠다.

 

풀이

각 좌표  마다 가장 가까운 냄새나는 사람과의 거리를 알아두면, 다익스트라 한번이면 해결된다.

가장 가까운 냄새나는 사람과의 거리는 BFS 돌면 된다. (각 냄새나는 사람마다 퍼지는 식)

솔직히 너무 간단해서 골1 정도 되는거 같다. 

 

빨리 꿀문제를 풀러 가보자!

 

+ 이 풀이는 어떤 지인분이 정해가 아닌 꼼수같은 풀이라고 합니다. (하지만 반례가 없ㄷ..)

 

코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
int n,m,k,sx,sy,ex,ey;
int nx[8] = {1,0,-1,0,1,1,-1,-1}, ny[8] = {0,1,0,-1,1,-1,1,-1};
int c[1005][1005],d[1005][1005],INF = 1e9;
pi tr[1000005];

int dist(pi x,pi y) {
    return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    cin >> sx >> sy >> ex >> ey;
    cin >> k;
    queue <pair<pi,int>> q2;
    priority_queue <pair<int,pi>> q;
    for(int i = 1;i <= k;i++) {
        int x,y; cin >> x >> y;
        tr[i] = {x,y};
        q2.push({{x,y},i});
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) d[i][j] = INF;
    }
    while(!q2.empty()) {
        int x = q2.front().x.x,y = q2.front().x.y, wi = q2.front().y; q2.pop();
        if(d[x][y] <= dist({x,y},tr[wi])) continue;
        d[x][y] = dist({x,y},tr[wi]);
        for(int i = 0;i < 8;i++) {
            int dx = x+nx[i], dy = y+ny[i];
            if(dx < 1||dx > n||dy < 1||dy > m) continue;
            q2.push({{dx,dy},wi});
        }
    }
    q.push({d[sx][sy],{sx,sy}});
    while(!q.empty()) {
        int cost = q.top().x;
        int x = q.top().y.x, y = q.top().y.y;
        q.pop();
        if(c[x][y]) continue;
        c[x][y] = 1;
        if(x == ex&&y == ey) {
            cout << cost;
            return 0;
        }
        for(int i = 0;i < 4;i++) {
            int dx = x+nx[i], dy = y+ny[i];
            if(dx < 1||dx > n||dy < 1||dy > m||c[dx][dy]) continue;
            q.push({min(cost,d[dx][dy]),{dx,dy}});
        }
    }
}

출처 : 카톡 이모티콘 김춘배