[백준] 18405 경쟁적 전염

백준18405링크

문제

• NxN 크기의 시험관
• 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나
• 1초마다 상, 하, 좌, 우의 방향으로 증식
• 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다
• S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류

입력

1. N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000)
2. N개의 줄에 걸쳐서 시험관의 정보 (해당 위치에 바이러스가 존재하지 않는 경우 0)
3. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력(만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력)

풀이

우선 각 초마다 바이러스가 있는 위치에서의 BFS 구현
한 번의 BFS는 구현할 수 있지만 각 초마다의 BFS 구현의 반복을 어떻게 구현할지 어려웠다.
-> 각 초마다 반복하며 그 순간의 큐의 크기만큼 BFS 실행하여 구현

(몇 번의 런타임에러가 있었는데 그래프 크기를 NxM으로 착각하여 크기를 잘못 설정했음
틀린 경우는 바이러스가 1~K까지 각각 하나인 줄 알고 풀었는데, 같은 번호의 바이러스가 여러개인 경우도 존재 가능)

더 좋은 방법이 있을 것 같지만 이런 유형의 BFS 문제가 처음이었기 때문에 깔끔하지 못한 느낌이다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

int N, M, X, Y, S;

#define MAXN 201
#define MAXM 1001

using namespace std;

int g[MAXN][MAXM];
vector<pair<int, int>> virus[MAXM];

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };


void BFS() {

	queue<pair<int, int>> q; //바이러스 위치 저장 큐
	queue<int> indexq; // 각 바이러스의 번호 저장 큐

	//바이러스의 위치를 큐에 저장
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < virus[i].size(); j++) {
			q.push(make_pair(virus[i][j].first, virus[i][j].second));
			indexq.push(i);
		}
	}

	for (int i = 0; i < S; i++) { //시간이 S초만큼 반복
		int qsize = q.size(); //각 초에서의 큐의 크기

		while (qsize) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			int index = indexq.front();
			indexq.pop();

			//BFS 탐색
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
					continue;
				}
				if (g[nx][ny] == 0) {
					g[nx][ny] = index;
					q.push(make_pair(nx, ny));
					indexq.push(index);
				}
			}
			qsize--;
		}
	}

	return;

}

int main() {
	cin >> N >> M;

	int temp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> temp;
			g[i][j] = temp;
			if (temp > 0) {
				virus[temp].push_back(make_pair(i,j)); //1~K까지의 바이러스 위치 저장
			}
		}
	}

	cin >> S >> X >> Y;

	if (S == 0) { //초가 0인경우는 BFS 실행 X
		cout << g[X - 1][Y - 1];
	}
	else {
		BFS();
		cout << g[X - 1][Y - 1];
	}
	

	return 0;
}