알고리즘 :: 백준 :: BFS :: 18405 :: 경쟁적 전염

문제

N x N 크기의 시험관이 있다. 시험관은 1 x 1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.
시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X, Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오.

문제접근

문제의 조건 네 가지는 다음과 같다.
1. 바이러스는 1번부터 K번까지 번호가 주어진다.
2. 바이러스는 상, 하, 좌, 우 4 방향으로 증식한다.
3. 번호가 낮은 종류의 바이러스부터 먼저 증식한다.
4. 이미 바이러스가 존재하는 칸에는 다른 바이러스가 들어갈 수 없다.

실수한 풀이과정

• 3번 조건을 위해서는 입력받은 바이러스를 번호순으로 순서대로 정렬할 수 있어야 한다.
• 그러나 이를 번호가 낮은 바이러스는 번호가 높은 바이러스가 있는 위치를 덮어씌울 수 있다고 생각하면 굳이 복잡하게 바이러스를 정렬할 필요가 없고 깔끔하다.
• 하지만, 4번 조건을 위배하게 되므로 이 방법은 올바른 방법이 아니다.

정답 풀이과정

• 바이러스의 좌표와 번호를 tuple 자료구조로 vector 컨테이너에 저장한다.
• sort()함수를 사용해서 번호에 대해 오름차순으로 정렬한다.
• 정렬한 결과를 queue<tuple<int, int, int>>에 push한다.
• 이제 queue에 바이러스가 번호순으로 저장되어 있으므로 BFS를 수행한다.
• 이때, 시간을 카운트 해줘야 한다.
  1. K는 바이러스의 개수를 의미하며 동시에 마지막 바이러스 번호를 의미한다.
  2. prevVirusType 변수를 사용해서 이전에 BFS를 돌린 바이러스를 기록한다.
  3. 현재 BFS를 수행하는 바이러스 번호 virusType와 prevVirusType이 다를 때 바이러스 개수를 카운트하고, 이 개수가 K개 이상일 때 시간을 증가시킨다.
• 목표 시간에 도달했다면 BFS 수행을 중지하고 답을 출력한다.

코드

2021/1/16 수정 코드 (with comment)

// Q17. 경쟁적 전염
#include <iostream>
#include <vector>       // for virus
#include <queue>        // for BFS
#include <tuple>
#include <algorithm>    // for sorting
using namespace std;

static int N, K, S, X, Y, test[201][201];
static vector<tuple<int, int, int>> virus;	// {num, y, x}
static constexpr int moving[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool isValid(int y, int x) {
	return (1 <= y && y <= N) && (1 <= x && x <= N);
}

void simulation() {
	queue<tuple<int, int, int>> q;
	for (const auto& v : virus) q.push(v);
	
	int prevVirusNum = 0;
	while(S != 0 && !q.empty()) {
		int vNum, curY, curX;
		tie(vNum, curY, curX) = q.front();
		q.pop();
		
                // if every virus has got its turn then subtract 'S'.
		if (prevVirusNum > vNum)    
			if (--S <= 0) break;    // End simulation as soon as 'S' reaches 0.
		prevVirusNum = vNum;
		
		for (int i = 0; i < 4; ++i) {
			int newY = curY + moving[i][0], newX = curX + moving[i][1];
			if (isValid(newY, newX) && test[newY][newX] == 0) {
				test[newY][newX] = vNum;
				q.push({vNum, newY, newX});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> K;
	for (int y = 1; y <= N; ++y)
		for (int x = 1; x <= N; ++x) {
			cin >> test[y][x];
			if (test[y][x] != 0) virus.push_back({test[y][x], y, x});
		}
	cin >> S >> Y >> X;    // X is row and Y is col in this problem.
	sort(virus.begin(), virus.end());    // Sort by first elem (virus num) of tuple.  
	simulation();
	cout << test[Y][X] << '\n';
}

9/18 수정 코드 (S 부분을 간결하게 다듬었습니다.)

int bfs() {
    while (!virus.empty() && S--) {
        int size = virus.size();
        while (size--) {
		int y, x, virusType; tie(y, x, virusType) = virus.front();
		virus.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + moving[i][0], nx = x + moving[i][1];
			if (isSafe(ny, nx) && lab[ny][nx] == 0) {
				virus.push({ny, nx, virusType});
				lab[ny][nx] = virusType;
			}
		}	
	}
    }
    return lab[Y][X];
}

// https://www.acmicpc.net/problem/18405
#include <iostream>
#include <tuple>
#include <queue>
#include <algorithm>
using namespace std;
using tupleElem = tuple<int, int, int>;
// NxN 시험관, K개 바이러스, S초, 좌표 (Y, X)
static int N, K, S, Y, X, lab[201][201];
static queue<tupleElem> virus;
static constexpr int moving[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

inline bool isSafe(int y, int x) {
    return ((1 <= y && y <= N) && (1 <= x && x <= N));
}

int bfs() {
    int virusCnt = 0, prevVirusType = 0, sec = 0;
    while (S != 0 && !virus.empty()) {
        int y, x, virusType; tie(y, x, virusType) = virus.front();
        virus.pop();
        // 바이러스 카운트 및 시간 증가
        if (virusCnt == 0 || prevVirusType != virusType) {
            prevVirusType = virusType;  // 이전 바이러스 기록 갱신
            virusCnt++;         	// 바이러스 카운트
            if (virusCnt > K) { 	// 바이러스 한 번씩 확산했으면 시간 증가 
                virusCnt = 1;   	// 바이러스 개수 1개로 다시 낮춰준다.
                sec++;
                if (sec == S) break;    // 목표 시간에 도달하면 진행 중지.
            }
        }
        for (int i = 0; i < 4; ++i) {
            int ny = y + moving[i][0], nx = x + moving[i][1];
            if (isSafe(ny, nx) && lab[ny][nx] == 0) {
                virus.push({ny, nx, virusType});
                lab[ny][nx] = virusType;
            }
        }
    }
    return lab[Y][X];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> K;
    vector<tupleElem> tempVirus;
    for (int y = 1; y <= N; ++y)
        for (int x = 1; x <= N; ++x) {
            cin >> lab[y][x];
            if (lab[y][x] != 0) tempVirus.push_back({y, x, lab[y][x]});
        }
    sort(begin(tempVirus), end(tempVirus), [](tupleElem lhs, tupleElem rhs) {
        return get<2>(lhs) < get<2>(rhs);
    });
    for (const auto& itr : tempVirus) virus.push(itr);
    cin >> S >> Y >> X;
    cout << bfs() << '\n';
}

결과