백준 18405 - 경쟁적 전염

문제링크

• 백준 18405

문제설명

• NxN 크기의 시험관이 있다. 특정한 위치에는 바이러스가 존재할 수 있다. 바이러스는 1부터 K번까지 중 하나에 속한다.
• 모든 바이러스는 1초마다 상,하,좌,우 방향으로 증식한다. 단, 매초마다 번호가 낮은 종류의 바이러스부터 증식한다. 증식 과정에서 이미 바이러스가 존재하는 칸에는 다른 바이러스가 들어갈 수 없다.
• S초가 지난 후에 (X, Y)에 위치한 바이러스의 종류를 출력하라

문제접근

• 번호가 낮은 바이러스부터 증식한다. —-> 증식 과정에서 먼저 증식한 바이러스는 다음에 증식할 바이러스에 영향을 준다.
• 번호 1부터 K번까지 시험관 전체를 탐색하며 번식을 할 수 있지만, 최악의 경우 K x N x N x S 번 각 칸을 탐색해야 하기 때문에 시간초과가 날 것이다.
• 한번의 탐색으로 모든 바이러스가 문제의 요구사항대로 번식할 수 있도록 해야 한다.
• 번식의 시작이 되는 바이러스 번호는 source[r][c] 2차원 배열에 담는다. 해당 배열에 담긴 바이러스는 (r,c)를 차지하는데 가장 우선순위가 높다.
• 바이러스가 번식되는 칸은 cand[r][c] 2차원 배열에 담는다. 해당 배열에 담긴 바이러스는 (r,c)로 증식하는 바이러스 중 번호가 가장 작은 바이러스가 담긴다.
• 시험관의 모든 칸에 대해서 번식 로직을 수행하고, source[r][c]와 cand[r][c]의 우선순위 정보를 이용해서 시험관을 업데이트 해준다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>

using namespace std;

int N, K, S, X, Y;
int board[201][201];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

bool cmp(int a, int b) {
	return a < b;
}

void spreadVirus() {
	int source[201][201]; // 번식을 시작한 지점
	int cand[201][201]; // 번식을 통해 추가되는 칸
	memset(source, 0, sizeof(source));
	memset(cand, 0, sizeof(cand));
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (board[r][c] == 0) continue;
			if (source[r][c] == 0) source[r][c] = board[r][c];
			else source[r][c] = min(source[r][c], board[r][c]);
			for (int dir = 0; dir < 4; dir++) {
				int nextX = r + dx[dir];
				int nextY = c + dy[dir];
				if (nextX<1 || nextX>N || nextY<1 || nextY>N) continue;
				if (cand[nextX][nextY] == 0) cand[nextX][nextY] = board[r][c];
				else cand[nextX][nextY] = min(cand[nextX][nextY], board[r][c]);
			}
		}
	}

	// update board
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (cand[r][c] == 0) {
				if (source[r][c] != 0) {
					board[r][c] = source[r][c];
				}
				continue;
			}
			if (source[r][c] != 0) board[r][c] = source[r][c];
			else {
				board[r][c] = cand[r][c];
			}
		}
	}
	// printBoard();
}

bool checkBoard() {
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (board[r][c] == 0) 
				return true;
		}
	}
	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d", &N, &K);
	memset(board, 0, sizeof(board));
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++)
			scanf("%d", &board[r][c]);
	}
	scanf("%d %d %d", &S, &X, &Y);
	for (int time = 0; time < S; time++) {
		if (checkBoard() == false) break;
		spreadVirus();
	}
	printf("%d\n", board[X][Y]);
	return 0;
}