취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18405번 문제인 경쟁적 전염이다.
문제는 아래 링크를 확인하자.

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

바이러스가 전염되는 순서에 우선순위가 있으므로, 해당 우선순위에 맞춰 주어진 바이러스들을 정렬하고 그 순서대로 확산해나가는 것을 반복하자.

BFS를 이용하면 한 단계씩 바이러스를 확산시켜나가는 구현을 하기 편리하다.

이 때, BFS의 깊이를 조절해 S초까지만 바이러스를 확산시켜나가면 문제를 간단히 해결할 수 있다.

상하좌우 칸 탐색의 구현은 아래의 코드에서 dr배열과 dc배열을 만든 것과 같이 구현하는 것으로 편리하게 할 수 있다.

아래는 제출한 소스코드이다.

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

int N, K, S, X, Y;
int arr[202][202];
vector<pair<int, pair<int, int>>> vec;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs() {
	sort(vec.begin(), vec.end());
	queue<pair<pair<int, int>, int>> que; // {{좌표},깊이}
	for (auto p : vec) {
		que.push(make_pair(p.second, 0));
	}

	while (!que.empty()) {
		int r = que.front().first.first, c = que.front().first.second, cnt = que.front().second;
		que.pop();
		if (cnt < S) {
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (rr<1 || rr>N || cc<1 || cc>N || arr[rr][cc]) continue;
				arr[rr][cc] = arr[r][c];
				que.push(make_pair(make_pair(rr, cc), cnt + 1));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int v; cin >> v;
			if (v) {
				arr[r][c] = v;
				vec.emplace_back(make_pair(v, make_pair(r, c)));
			}
		}
	}
	
	cin >> S >> X >> Y;

	bfs();

	cout << arr[X][Y];
}