(C++) 백준 18405 경쟁적 전염

문제 및 풀이

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

BFS

바이러스가 생긴 시간 + 바이러스의 우선순위를 기반으로 탐색해야 하는 문제.
virus 구조체를 정의해서 가장 먼저 생겼고, 우선순위가 낮은 바이러스 순으로 탐색했다.

코드

#include <iostream>
#include <queue>
using namespace std;

int arr[205][205]; int N;
bool check[205][205];
const int dx[4] = {0,0,1,-1};
const int dy[4] = {-1,1,0,0};


struct virus{
    int cnt;
    int y;
    int x;
    int val;

    virus(int a, int b, int c, int d) : cnt(a), y(b), x(c), val(d) {};

};


struct cmp{
    bool operator()(const virus &a, const virus &b){
        if(a.cnt==b.cnt) return a.val>b.val;
        else return a.cnt>b.cnt;
    }
};


int main(){
    ios_base::sync_with_stdio(0),
    cin.tie(0),
    cout.tie(0);

    int K;
    cin>>N>>K;


    priority_queue<virus, vector<virus>, cmp> pq;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>arr[i][j];
            if(arr[i][j]>0) pq.push(virus(0, i, j, arr[i][j]));
}
}

    int S,X,Y;
    cin>>S>>X>>Y;


    while(!pq.empty()){

        auto tmp = pq.top();
        pq.pop();
        if(tmp.cnt>=S) break;

        for(int k=0; k<4; k++){
            int y = tmp.y + dy[k];
            int x = tmp.x + dx[k];

            if(y<0 || y>=N || x<0 || x>=N) continue;
            if(arr[y][x]>0) continue;
            arr[y][x] = tmp.val;
            pq.push({tmp.cnt+1, y, x, arr[y][x]});
        }


    }


/*    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cout<<arr[i][j]<<" ";
        }
        cout<<'\n';
    }*/
    cout<<arr[X-1][Y-1];



}