[백준/C++] 18405 경쟁적 전염

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

코드

#include <iostream>
#include <queue>
using namespace std;

#define MAX 201
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
int n, k, s, x, y;
int arr[MAX][MAX];
int dx[4] = { 1, -1,0, 0 }, dy[4] = { 0, 0, 1, -1 };

queue<pair<int, int>> q[1001];
void bfs() {
	for (int i = 1; i < 1001; i++) {
		if (!q[i].empty()) {
			queue<pair<int, int>> tmp;
			while (!q[i].empty()) {
				int nx = q[i].front().first;
				int ny = q[i].front().second;

				q[i].pop();

				for (int j = 0; j < 4; j++) {
					int gx = nx + dx[j];
					int gy = ny + dy[j];

					if (gx >= 0 && gx < n && gy >= 0 && gy < n && !arr[gx][gy]) {
						arr[gx][gy] = i;
						tmp.push({ gx, gy });
					}
				}
			}
			q[i] = tmp;
		}
		
	}
}


int main() {
	FASTIO;
	
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] > 0) q[arr[i][j]].push({ i, j });
		}
	}

	cin >> s >> x >> y;

	while (s--) bfs();
	cout << arr[x - 1][y - 1];
	return 0;
}

 

설명

바이러스 정보가 주어지면 받고 바이러스 번호별 큐에 좌표를 저장한다. 이후 s번 bfs를 돌리면서 바이러스를 전파시킨다.

 

bfs에서는 낮은 번호의 바이러스부터 전파를 시작한다. 해당 바이러스가 존재한다면 큐가 끝날 때까지 전파를 시키고 tmp 큐에 새롭게 전파된 바이러스의 위치 좌표를 넣는다. 이후 tmp 큐를 q[i]에 대입해서 다음에 전파를 시작할 위치들을 저장한다.

 

느낀 점

문제 자체는 어렵지 않았는데, 코드를 한 번에 작성한 게 아니라 시간 날 때마다 써서 그런지 놓친 부분이 몇 군데 있어서 두 번 틀렸다..