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

18405번: 경쟁적 전염

bfs를 활용한 구현 문제이다. 반복문을 많이 사용해 시간 초과가 발생할 줄 알았는데 한번에 통과했다. 먼저 맵을 입력 받으면서 해당 바이러스의 번호를 구분하여 좌표를 벡터에 저장해주었다. 그 후 반복문을 돌면서 bfs를 사용하게 되는데 이 때 바이러스를 백터 1번째 원소부터, 즉 바이러스 1부터 bfs를 돌면서 A에 전염된 바이러스를 저장해주고 이를 tmp를 사용하여 v에 저장해주었다. 이를 반복한 후 출력해주었다. 쉽게 풀 수 있었던 문제였다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, K, S, X, Y;
int A[201][201];
vector<pair<int, int>> v[1001];
vector<pair<int, int>> tmp;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

void bfs(int a, int b) {
    queue<pair<int, int>> q;
    int n = A[a][b];

    q.push({ a,b });

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny <= 0 || nx <= 0 || ny > N || nx > N) continue;
            if (A[ny][nx] != 0) continue;

            A[ny][nx] = n;
            tmp.push_back({ ny, nx });
        }
    }
}

void solution() {
    for (int i = 0; i < S; i++) {
        for (int j = 1; j <= K; j++) {
            for (int k = 0; k < v[j].size(); k++) {
                bfs(v[j][k].first, v[j][k].second);

                v[j].erase(v[j].begin());
                k--;
            }

            for (int k = 0; k < tmp.size(); k++) {
                v[j].push_back({ tmp[k].first, tmp[k].second });
            }
            tmp.clear();
        }
    }

    cout << A[X][Y];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];

            v[A[i][j]].push_back({ i,j });
        }
    }

    cin >> S >> X >> Y;

    solution();

    return 0;
}