[C++]백준2234번 성곽

문제는 다음과 같다.

오늘은 백준2234번 성곽 문제를 풀어보도록 하자.

일반적인 BFS와 비트마스킹을 섞어놓은 문제이다. map의 숫자를 보면 서쪽 : + 1, 북쪽 : +2, 동쪽 : +4, 남쪽 : +8 로 벽의 위치를 알 수 있다.

즉, 2^n승으로 벽을 체크할 수 있는데 이것은 곧 비트마스킹으로 벽을 체크할 수 있다는 소리이다. 따라서 문제의 1번과 2번은 map[i][j] & bit 로 0이면

뚫려있다는 얘기이므로 큐에 넣어주며 방을 체크하면 되고 3번은 만일 비트마스킹을 했는데 1이면 벽이 있다는 얘기이므로 벽을 제거하고 방의 갯수를 카운트하고

다시 벽을 세우고 dfs식으로 탐색하면 된다.

                                     [코드]
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int map[50][50];
int visit[50][50];
int dir[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int R, C, temp_rooms = 0, large_rooms = 0, cnt_rooms = 0, wall_del_rooms = 0;
struct pos {
	int y;
	int x;
};
queue<pos>Q;

bool Inbound(int y, int x) {
	return y >= 0 && y < R && x >= 0 && x < C;
}

void bfs(int y, int x) {
	Q.push({ y, x });
	visit[y][x] = true;
	temp_rooms = 0;

	while (!Q.empty()) {
		int y = Q.front().y;
		int x = Q.front().x;

		Q.pop();

		int bit = 1;

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (Inbound(my, mx)) {
				if (!(map[y][x] & bit)) {
					if (!visit[my][mx]) {
						Q.push({ my,mx });
						visit[my][mx] = true;
					}
				}
			}
			bit <<= 1;
		}
		temp_rooms++;
	}
}

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

	cin >> C >> R;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (!visit[i][j]) {
				bfs(i, j);
				cnt_rooms++;
				if (temp_rooms > large_rooms) large_rooms = temp_rooms;
			}
		}
	}
	cout << cnt_rooms << '\n';
	cout << large_rooms << '\n';

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			for (int k = 1; k <= 16; k <<= 1) {
				if (map[i][j] & k) {
					memset(visit, false, sizeof(visit));
					map[i][j] -= k;
					bfs(i, j);
					map[i][j] += k;
					if (temp_rooms > wall_del_rooms) wall_del_rooms = temp_rooms;
				}
			}
		}
	}
	cout << wall_del_rooms << '\n';
}