백준 경쟁적 전염

이 문제는 BFS로 접근해 풀었다.

 

맵이 주어지고 바이러스의 번호가 주어진다. 모든 바이러스는 동시 다발적으로 퍼지지만 번호가 낮은 바이러스부터 퍼진다.

 

그래서 바이러스의 입력위치와 값을 저장하는 벡터와 다음값을 저장해줄 벡터 2개를 구현해 BFS로 풀었다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int dx[8] = { 1, 0, -1, 0,-1,-1,1,1 };
int dy[8] = { 0, 1, 0, -1,-1,1,-1,1 };
int cnt;
int n, m, t;
int dp[201][201];
bool visited[201][201];

int main() {
	cin >> n >> m;
	int s, x, y;
	vector<tuple<int, int, int>> res;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> dp[i][j];
			if (dp[i][j] != 0) {
				res.push_back({ i,j,dp[i][j] });
			}
		}
	}
	cin >> s >> x >> y;
	
	for (int i = 0; i < s; i++) {
		vector<tuple<int, int, int>> temp;
		sort(res.begin(), res.end(), [](auto& left, auto& right) {
			return get<2>(left) < get<2>(right); });


		for (const auto& it : res) {
			int cx = get<0>(it);
			int cy = get<1>(it);
			for (int d = 0; d < 4; d++) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];

				if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
					// 0
					if (dp[nx][ny] == 0) {
						dp[nx][ny] = get<2>(it);
						temp.push_back({ nx,ny,get<2>(it) });
					}
				}
			}
		}

		res.clear();
		res = temp;
	}

	cout << dp[x - 1][y - 1];
	return 0;
}

 

벡터에 값을 입력하고 바이러스 번호순으로 정렬을 해준다. 그리고 주어진 시간초만큼 바이러스를 전파시킨후 해당 위치의 값을 보여주면 끝이다.