[C++] BOJ(백준) 2234 성곽

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

2234번: 성곽

 

비트마스킹을 이용한 BFS 문제다.

 

흔히 우리가 아는 2차원 배열에서 영역을 구하는 문제다.

그러나 인접한 모든 곳으로 지나갈 수 있는 것이 아니고 벽으로 막혀 있는 방의 영역을 구하는 문제다.

이 문제의 특징은 막힌 칸이 있는 것이 아니라 인접한 방 사이를 갈 수 없는 벽이 존재한다.

따라서 입력이 2차원 배열의 크기만큼 각 칸의 벽을 나타내는 정수가 들어온다.

좌1 상2 우4 하8로 2의 제곱수, 비트마스킹의 합으로 정보를 나타낸다.

해당 숫자를 2진수로 바꾸면 해당 칸에서 이동할 수 있는 칸의 정보를 알 수 있다.

 

위 정보를 토대로 BFS를 실행한다.

BFS 실행 횟수만큼 방의 개수를 파악할 수 있다.

BFS를 실행하면서 방의 크기를 구할 수 있기 때문에 가장 넓은 방의 넓이도 구할 수 있다.

하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기는

BFS를 돌면서 각 방의 크기를 각 칸에 저장해 상하좌우를 비교하며 합이 가장 큰 값을 찾았다.

 

여기서 생겼던 문제는 배열에 각 방의 크기를 저장했기 때문에 크기가 같으면 같은 방이라고 생각을 해

값이 다른 경우에만 합을 구했다. 그러나 크기가 같은 방이 나란히 있을 수 있기 때문에 배열을 하나 더 생성했다.

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int n, m, areaCnt;
string arr[50][50];
int visit[50][50];
int area[50][50];
int maxSize;

int dr[4] = { 1, 0, -1, 0 };
int dc[4] = { 0, 1, 0, -1 };

void BFS(int i, int j) {
	queue<pair<int, int>> q;
	q.push({ i, j });
	visit[i][j] = -1;

	int cnt = 1;
	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			if (arr[r][c][i] == '1') continue;

			int rr = r + dr[i];
			int cc = c + dc[i];

			if (rr < 0 || cc < 0 || rr >= n || cc >= m) continue;
			if (visit[rr][cc]) continue;
			
			visit[rr][cc] = -1;
			q.push({ rr, cc });

			cnt++;
		}
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (visit[i][j] == -1) {
				visit[i][j] = cnt;
				area[i][j] = areaCnt;
			}
	areaCnt++;
	maxSize = max(maxSize, cnt);
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			int a;	cin >> a;
			while (a) {
				arr[i][j] = to_string(a % 2) + arr[i][j];
				a /= 2;
			}
			while (arr[i][j].size() < 4) arr[i][j] = "0" + arr[i][j];
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (visit[i][j] == 0) {
				BFS(i, j);
			}

	int remove = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 4; k++) {
				int rr = i + dr[k];
				int cc = j + dc[k];

				if (rr < 0 || cc < 0 || rr >= n || cc >= m) continue;
				if (area[i][j] == area[rr][cc]) continue;

				remove = max(remove, visit[i][j] + visit[rr][cc]);
			}
		}
	}

	cout << areaCnt << "\n" << maxSize << "\n" << remove;
}