[BOJ/Gold 3] 백준 24513 좀비 바이러스(C++)

문제 링크

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

24513번: 좀비 바이러스

 

 

여기 N x M 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 1번, 2번, 3번으로 번호를 매겼다. 

바이러스의 특징은 다음과 같다.

•  1번과 2번 바이러스는 치사율은 낮지만 전염성이 강해 상하좌우에 인접해 있는 마을로 동시에 퍼져나가며 한 마을을 완전히 감염시키는 데 1시간 걸린다.
• 마을이 완전히 감염되어야 다른 마을로 퍼져나갈 수 있으며 다른 바이러스가 완전히 감염시킨 마을은 침범하지 않는다.
• 마을이 한 바이러스에 완전히 감염되기 전에 다른 종류의 바이러스가 마을에 도착하면 3번 바이러스가 만들어진다.
•  3번 바이러스는 치사율이 높은 만큼 전염성이 약해 감염된 마을에서 더 이상 퍼지지 않는다.
• 치료제를 갖고 있는 마을은 감염시킬 수 없다.

 1번 바이러스와 2번 바이러스에 감염된 마을이 나와버렸다. 바이러스가 퍼질 수 있는 대로 퍼졌을 때 1번, 2번, 3번 바이러스에 감염된 마을이 각각 몇 개일지 구해보자.

입력

첫째 줄에 N(2 ≤ N ≤ 1000)과 M(2 ≤ M ≤ 1000)이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 마을의 상태가 M개 주어진다. 마을의 상태는 다음과 같이 이루어져 있다.

•  −1: 치료제를 가진 마을
•  0: 아직 감염되지 않은 마을
•  1: 1번 바이러스에 감염된 마을
•  2: 2번 바이러스에 감염된 마을

 1번 바이러스와 2번 바이러스에 감염된 마을은 각각 하나씩만 주어진다.

출력

 1번, 2번, 3번 바이러스에 감염된 마을의 수를 공백으로 구분하여 한 줄에 출력한다.

예제 입력 1

4 4
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 2

예제 출력 1

10 3 3

예제 입력 2

7 9
0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 -1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 -1 0 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 -1 0 0
0 0 0 0 0 0 0 0 0

예제 출력 2

25 29 6

알고리즘 분류

• 그래프 탐색

풀이

먼저 현재 존재하는 바이러스들의 좌표와 시간을 큐에 push한다. 그리고 BFS를 수행한다.

현재 바이러스의 상하좌우로 1칸 옆에 있는 집에 바이러스가 퍼진다. 다만 집에 치료제가 존재하는 경우에는 퍼질 수 없다.

집에 아무것도 없다면 퍼진다. 집에 3번 바이러스를 제외하고 다른 바이러스가 존재할 때, 이 바이러스가 완전하게 집을 감염시키지 않았다면 3번 바이러스로 바뀌면서 전염을 멈춘다.

바이러스가 집을 완전하게 전염시켰을 때의 시각을 기록하기 위해 visited라는 2차원 배열을 선언한다.

집이 비어있을 때 해당 집을 현재 바이러스로 초기화하고 현재 바이러스가 현재 집을 완전히 전염시켰을 때의 시각에서 1 증가된 수치를 기록한다.

집에 다른 바이러스가 존재할 때 visited[Y][X]가 현재 바이러스가 완전히 전염시켰을 때의 시각보다 1 많다면 다음 집의 바이러스는 3번으로 변하면서 전염을 멈춘다. 즉 큐에 push하지 않는다.

집에 3번 바이러스가 있거나 치료제가 있다면 그 쪽으로는 바이러스가 전염될 수 없다.

BFS를 완전히 종료한 후 모든 집을 탐색하여 1번, 2번, 3번 바이러스의 개수를 구하고 공백으로 나누어 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1001
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int MAP[MAX][MAX];
int visited[MAX][MAX];
queue<pair<pair<int, int>, int> > Q;
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == 1) {
                Q.push(make_pair(make_pair(i, j), 1));
                visited[i][j] = 1;
            }
            else if (MAP[i][j] == 2) {
                Q.push(make_pair(make_pair(i, j), 1));
                visited[i][j] = 1;
            }
        }
    }
}

void BFS() {
    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowT = Q.front().second;
        Q.pop();

        if (MAP[NowY][NowX] == 3) {
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            int Which = MAP[NowY][NowX];
            if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < M)) {
                if (MAP[NextY][NextX] == 0) {
                    visited[NextY][NextX] = NowT + 1;
                    Q.push(make_pair(make_pair(NextY, NextX), NowT + 1));
                    MAP[NextY][NextX] = Which;
                }
                else if ((MAP[NextY][NextX] == 1) && (Which == 2)) {
                    if (visited[NextY][NextX] == NowT + 1) {
                        MAP[NextY][NextX] = 3;
                    }
                }
                else if ((MAP[NextY][NextX] == 2) && (Which == 1)) {
                    if (visited[NextY][NextX] == NowT + 1) {
                        MAP[NextY][NextX] = 3;
                    }
                }
            }
        }
    };
}

void find_Answer() {
    int A = 0;
    int B = 0;
    int C = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (MAP[i][j] == 1) {
                A++;
            }
            else if (MAP[i][j] == 2) {
                B++;
            }
            else if (MAP[i][j] == 3) {
                C++;
            }
        }
    }
    cout << A << " " << B << " " << C << "\n";
}

int main() {
    FASTIO
    input();
    BFS();
    find_Answer();

    return 0;
}