[Algorithm] 백준 18405 경쟁적 전염 - C++

18405번: 경쟁적 전염

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

int n, k;
int s, x, y;
int map[201][201];
int moveY[] = { 0, 0, 1, -1 };
int moveX[] = { 1, -1, 0, 0 };

bool IsOut(int y, int x){
    if(x < 1 || y < 1 || x > n || y > n)
        return true;
    return false;
}

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

    // input
    cin >> n >> k;
    vector<pair<int, pair<int, int>>> virus;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> map[i][j];
            if(map[i][j] != 0)
                virus.push_back({map[i][j], {i, j}});
        }
    }
    cin >> s >> y >> x;

    // solution
    sort(virus.begin(), virus.end());
    int curTime = 0;
    while (curTime < s){
        int virusCount = virus.size();
        for(int i = 0; i < virusCount; i++){
            int curVirus = virus[i].first;
            int curY = virus[i].second.first;
            int curX = virus[i].second.second;

            for(int i = 0; i < 4; i++){
                int nextY = curY + moveY[i];
                int nextX = curX + moveX[i];

                if(IsOut(nextY, nextX)) continue;
                if(map[nextY][nextX])   continue;

                map[nextY][nextX] = curVirus;
                virus.push_back({curVirus, {nextY, nextX}});
            }
        }
        if(map[y][x])   break;
        curTime++;
    }
    
    // print
    cout << map[y][x] << '\n';
}

---

 처음에는 그냥 큐를 이용해서 1턴에 해당하는 큐 사이즈를 받고 그만큼 pop을 하면서 1턴을 계산하려고 했습니다. 그런데 그러면 바이러스 순서를 고려하기 어려워졌고 그 순서를 관리해주기 위해서 힙을 사용하려고 했는데 힙은 들어갈때마다 순서 고려를 하니 턴을 관리하기가 어려웠습니다.

 

 그래서 위 코드처럼 벡터를 통해서 이걸 한번 정렬해주고 그 벡터를 사용하는 방식을 사용하기로 했습니다. 관련 궁금증은 아래 목록에서 해결이 가능할거라 봅니다.

 

- 벡터 정렬은 왜 한번만 하냐? : 첫턴만 정렬해 두면 이후에는 그 정렬된 대로 push_back 되기 때문에 이후에는 정렬해줄 필요가 없습니다.

- 이미 한번 본곳도 있어서 비효율적이지 않나? : 검색량이 많지 않아 위 방식대로 사용하게 되었습니다. 벡터에 중복 추가되는 원소는 없어서 괜찮습니다.

    - 따로 변수를 두개 둬서 이번 턴에 탐색할 원소 시작, 끝을 저장해 하면 시간 이득이 있을 수는 있겠지만 귀찮아서...