[BAEKJOON] 2234번 성곽

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

 

문제조건

1.  굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로
2. 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다.
3. 1. 이 성에 있는 방의 개수
   2. 가장 넓은 방의 넓이
   3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 각각 구하시오

접근방법

 

전체 맵을 탐색한다는 점에서 BFS를 떠올릴 수 있었고, 1(2^0), 2(2^1), 4(2^2), 8(2^3) 로 진행할수 있는지 판단해야한다는 점에서 나에겐 조금 생소한 비트마스킹이 생각났다.

 

이 문제에서 핵심은 비트를 1부터 왼쪽으로 Shift연산을 통해 벽에 대해 나타낸 숫자와 &연산으로 겹치는 지 확인 하는 것이다. 또한 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기는 Brute Force 방식으로 각 방에 대해서 하나씩 벽을 없애고 최댓값을 갱신했다.

 

소스코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int map[51][51], visited[51][51];
int n, m, big, res;
int dy[] = { 0, -1, 0, 1 };
int dx[] = { -1, 0, 1, 0 };

int bfs(int y, int x) {
	queue<pair<int, int> > q;
	q.push({ y,x });
	visited[y][x] = 1;
	int cnt = 1;
	while (!q.empty()) {
		int cury = q.front().first;
		int curx = q.front().second;
		q.pop();
		int bit = 1;
		for (int i = 0; i < 4; i++) {
			if (!(map[cury][curx] & bit)) {
				int ny = cury + dy[i];
				int nx = curx + dx[i];
				if (ny >= m || ny < 0 || nx >= n || nx < 0) continue;
				if (!visited[ny][nx]) {
					visited[ny][nx] = 1;
					q.push({ ny,nx });
					cnt++;
				}
			}
			bit <<= 1;
		}
	}
	return cnt;
}

int main(){
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				big = max(big, bfs(i, j));
				res++;
			}
		}
	}
	cout << res << '\n' << big << '\n';
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			for (int bit = 1; bit <= 8; bit <<= 1) {
				if (map[i][j] & bit) {
					memset(visited, 0, sizeof(visited));
					map[i][j] -= bit;
					big = max(big, bfs(i, j));
					map[i][j] += bit;
				}
			}
		}
	}
	cout << big;
}