경쟁적 전염 (feat. 백준, 18405번)

경쟁적 전염
https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <set>
#include <tuple>
#include <algorithm>
using namespace std;
int N, S, X, Y, dx[4], dy[4], ans[200][200];
bool visit[200][200];
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    register int K;
    cin >> N >> K;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < N; ++j)
            cin >> ans[i][j], visit[i][j] = false;
    cin >> S >> X >> Y;
    for(register int s = 0, i, j; s < S; ++s){
        set<tuple<int, int, int>> tmpl;
        for(i = 0; i < N; ++i)
            for(j = 0; j < N; ++j)
                if(!visit[i][j] && ans[i][j] != 0)
                    tmpl.insert(make_tuple(ans[i][j], i, j));
        for(auto& p : tmpl){
            auto v = get<0>(p), x = get<1>(p), y = get<2>(p);
            visit[x][y] = true;
            for(register int d = 0, nx, ny; d < 4; ++d){
                nx = x + dx[d], ny = y + dy[d];
                if(0 <= nx && nx < N && 0 <= ny && ny < N && ans[nx][ny] == 0)
                    ans[nx][ny] = v;
            }
        }
    }
    cout << ans[X - 1][Y - 1];
    return 0;
}
// *&)*@*

 

반응형

1. 1초가 지날때마다 모든 숫자가 전염됩니다.
2. 다만 이전에 전염을 시킨 숙주는 다음번에 활동을 못한다고 생각하면 고려 대상이 줄어들게 됩니다.
3. 즉, 이전 시간에 전염 당한 아이들이 현재 시간에 전염을 시키는 숙주가 됩니다.
4. 저는 숙주의 숫자를 정렬하기 위해 자료구조 set을 사용하였지만 priority_queue 등도 가능합니다.