편세권 C++ - 백준 31849

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

대회 때 못 푼 문제.

문제 접근

처음에는 모든 편의점에서 BFS를 시도했지만 TLE가 났다.

따라서 다른 방법이 필요했다.

문제 제한에서 $NM<=1e6$이 기 때문에 BFS를 각 편의점마다 수행할 수 없다.

다른 방법

과연 어떤 방법이 필요한가?

우선 BFS의 특성을 살펴보자,

0-1 BFS는 항상 출발지에서 도착지까지 최단 거리를 구한다는 특징이 있다.

그러면 여러 점에서 BFS를 동시에 수행하면 어떻게 될까?

이 역시 여러 점에서 도착지까지 최단 거리를 보장할 수 있다.

처음에는 이 점이 잘 와닿지 않았는데, 조금만 생각해보면 왜 그런지 알 수 있다.

만약 어떤 점 $A,B$에서 BFS를 시작한다고 하고,

$C$에서 도착한다고 하자.

$B$에서 BFS를 수행했다고 해서 $C$로 가는 최단 경로가 과연 방해되는가?

BFS의 구현을 시각화해보면 쉽게 풀리는 의문점이다.

$C$로 가는 최단거리는 방해될리 없다.

왜냐하면 먼저 도착한 $B$가 $C$까지의 최단 거리 점이기 때문이다.

구현

이 점에 착안하여 모든 편의점에서 BFS를 수행해 방까지의 거리를 구해주고,

답을 구해주면 된다.

코드는 다음과 같다.

// TLE CODE
// #include <bits/stdc++.h>
// typedef long long ll;
// using namespace std;

// struct poi{
//     int x,y;
// };

// int main(){
//     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//     int n,m,r,c;
//     cin >> n >> m >> r >> c;
//     vector<vector<bool>> convi(n+1,vector<bool> (m+1,0));
//     vector<int> p(r);
//     vector<poi> room(r);
//     for(int i=0;i<r;i++){
//         cin >> room[i].x >> room[i].y >> p[i];
//     }
//     int t=2200;
//     int dx[]={1,-1,0,0};
//     int dy[]={0,0,1,-1};
//     while(c--){
//         int x,y;
//         cin >> x >> y;
//         convi[x][y]=1;
//     }
//     for(int i=0;i<r;i++){
//         queue<poi> q;
//         vector<vector<bool>> vis(n+1,vector<bool> (m+1,0));
//         q.push({room[i].x,room[i].y});
//         vis[room[i].x][room[i].y]=1;
//         int mini=0;
//         bool e=0;
//         while(!q.empty() && !e){
//             poi now=q.front();
//             q.pop();
//             for(int j=0;j<4;j++){
//                 int nx=now.x+dx[j];
//                 int ny=now.y+dy[j];
//                 if(n<nx || nx<1 || m<ny || ny<1) continue;
//                 if(vis[nx][ny]) continue;
//                 if(convi[nx][ny]){
//                     if(mini!=0 && mini<abs(room[i].x-nx)+abs(room[i].y-ny)){
//                         e=1;
//                         break;
//                     }
//                     mini=abs(room[i].x-nx)+abs(room[i].y-ny);
//                     t=min(t,mini*p[i]);
//                 }
//                 vis[nx][ny]=1;
//                 q.push({nx,ny});
//             }
//         }
//     }
//     cout << t;
//     return 0;
// }

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct poi{
    int x,y;
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,r,c;
    cin >> n >> m >> r >> c;
    vector<vector<int>> d(n+1,vector<int> (m+1));
    vector<vector<bool>> vis(n+1,vector<bool> (m+1,0));
    vector<poi> room(r);
    vector<int> p(r);
    queue<poi> q;
    for(int i=0;i<r;i++) cin >> room[i].x >> room[i]. y >> p[i];
    while(c--){
        int xx,yy;
        cin >> xx >> yy;
        q.push({xx,yy});
        d[xx][yy]=0;
        vis[xx][yy]=1;
    }
    int ans=200000;
    int dx[]={1,-1,0,0};
    int dy[]={0,0,1,-1};
    while(!q.empty()){
        poi now=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int nx=now.x+dx[i];
            int ny=now.y+dy[i];
            if(n<nx || nx<1 || m<ny || ny<1) continue;
            if(vis[nx][ny]) continue;
            d[nx][ny]=d[now.x][now.y]+1;
            q.push({nx,ny});
            vis[nx][ny]=1;
        }
    }
    for(int i=0;i<r;i++){
        int xx=room[i].x;
        int yy=room[i].y;
        ans=min(ans,d[xx][yy]*p[i]);
    }
    cout << ans;
    return 0;
}