[백준 24513] 좀비 바이러스

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

24513번: 좀비 바이러스

#include <cstdio>
#include <queue>
#include <cstring>
int R, C;
int board[1000 + 2][1000 + 2];

struct _st
{
	int type;
	int x, y;
	int time;
};
std::queue<_st> Q;
int visited[1000 + 2][1000 + 2];


void input()
{
	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 1 || board[i][j] == 2) {
				Q.push({ board[i][j], i, j, 1 });
				visited[i][j] = 1;
			}
		}
	}
}


void BFS()
{
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (board[data.x][data.y] == 3) continue;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];


			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == -1) continue;				// 치료제 있는 마을 
			if (visited[nx][ny] == 0) {		// 빈 마을
				board[nx][ny] = data.type;
				Q.push({ data.type, nx, ny, data.time + 1 });
				visited[nx][ny] = visited[data.x][data.y] + 1;
			}
			else {	// 감염된 마을 
				if (visited[nx][ny] < data.time + 1) continue;	
				if (board[nx][ny] == data.type && visited[nx][ny] < data.time + 1) continue;
				if (board[nx][ny] != 3 && board[nx][ny] != data.type && visited[nx][ny] == data.time + 1) board[nx][ny] = 3;
			}
		}
	}
}

void output()
{
	int one = 0, two = 0, three = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 1) one++;
			else if (board[i][j] == 2) two++;
			else if (board[i][j] == 3) three++;
		}
	}
	printf("%d %d %d\n", one, two, three);
}



int main()
{
	input();
	BFS();
	output();
	return 0;
}

3번 바이러스는 퍼지지 않는다. 

그렇다면 상태를 더 발전해 보아야 할까 ? 

 

---

좀비 바이러스를 풀었다면 ? => 좀 더 생각해보아야 할 문제 추천

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

18809번: Gaaaaaaaaaarden

https://kimsouce.tistory.com/335

[백준 18809] Gaaaaaaaaaarden