취미로 코딩하기

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

이번에 볼 문제는 백준 15806번 문제인 영우의 기숙사 청소이다.
문제는 아래 링크를 확인하자.

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

일반적으로, 현재 단계에 피어있는 곰팡이는 다다음 단계에 그 위치에 그대로 다시 피어나게 된다는 점을 관찰하자. 해당 곰팡이가 퍼뜨린 포자가 다음 단계에 다시 원위치에도 포자를 퍼뜨리기 때문이다.

위의 관찰을 이용해, 짝수단계와 홀수단계에 퍼져있는 곰팡이의 모습을 각각 bfs를 통해 퍼뜨리는 것으로 문제를 해결할 수 있다.

단, 현재 단계에 피어있는 곰팡이가 포자를 퍼뜨릴 수 없는 경우는 예외이다. 초기 상태에서만 그러한 경우를 찾을 수 있는데, 그 외의 경우 이전 단계에서 해당 위치로 곰팡이 포자가 퍼져왔을 수밖에 없기 때문이다. 이에 대한 예외처리를 적절히 생각하고 구현해 문제를 해결하자.

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

#define MP(x,y) make_pair(x,y)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M, K, T;
queue<pair<int, int>> que;
bool odd[301][301];
bool even[301][301];

int dr[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dc[8] = { 2,1,-1,-2,-2,-1,1,2 };

void oddbfs() {
	int rep = que.size();
	while (rep--) {
		auto& p = que.front();
		int r = p.first, c = p.second;
		que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr<1 || rr>N || cc<1 || cc>N) continue;
			if (odd[rr][cc]) continue;
			odd[rr][cc] = 1;
			que.push(MP(rr, cc));
		}
	}
}

void evenbfs() {
	int rep = que.size();
	while (rep--) {
		auto& p = que.front();
		int r = p.first, c = p.second;
		que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr<1 || rr>N || cc<1 || cc>N) continue;
			if (even[rr][cc]) continue;
			even[rr][cc] = 1;
			que.push(MP(rr, cc));
		}
	}
}

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

	cin >> N >> M >> K >> T;;
	while (M--) {
		int r, c; cin >> r >> c;
		que.push(MP(r, c));
	}
	for (int t = 1; t <= T; t++) {
		if (t & 1) oddbfs();
		else evenbfs();
	}

	bool ans = 1;
	while (K--) {
		int r, c; cin >> r >> c;
		if (T & 1) {
			if (odd[r][c]) ans = 0;
		}
		else {
			if (even[r][c]) ans = 0;
		}
	}

	if (ans) cout << "NO";
	else cout << "YES";
}