[백준 2234번 / C++] 성곽

 

 

이 문제는 "비트연산, 완전탐색, BFS"를 활용한 문제이다. 

 

이 세가지에 대한 이해도가 확실하면 정말 재밌게 풀 수 있을것이다.  먼저 구해야 할 값은 총 3가지이다. 

1. 처음 BFS 함수를 호출 하는 개수(방의 개수) 

2. BFS함수에서 Queue값을 pop() 하는 개수(방의 영역)

3. 하나의 벽을 허물었을 때 나오는 최대 방의 영역. 

 

먼저 , 첫 번째 답과 두 번째 답을 풀기 어렵다면 쉬운 bfs 문제를 풀고 오기를 권한다. 

 

이 문제에서 조금 다른점은 벽의 위치를 2진수 방법으로 표현했다는 것이다.

예를들어, 10진수 "11"은  2진수로 "1011" 이라는 값이 나오는데

오른쪽부터 위치한 1은 서쪽에 벽이있고 그 다음 1은 북쪽에 벽이 있고 그 다음 0은 동쪽에 벽이 없고 그 다음 1은 남쪽에 벽이 있다는 뜻이다. 

 

즉, 10진수의 값을 AND연산자를 활용해서 해당 서,북,동,남 으로 벽의 위치를 확인하고 벽이 있으면 continue 하고 벽이 없으면 맵을 초과하진 않았는지, 방문한적 없는지를 체크해서 조건 만족시 queue에 담고 다음 좌표로 이동하게 된다. 

 

3번의 답은 완전 탐색을 통해서 풀면 된다. 

map에 저장된 값들을 모두 탐색하면서 벽이 있는지 없는지 확인한다. 

벽이 있다면 하나를 제거 후 bfs()를 호출하고 리턴된 후에는 벽을 제거한 값을 다시 복구 시켜준다. 

 

이 문제는 XOR , OR, AND 연산자를 잘 활용해서 문제를 풀면 재밌게 풀린다.  

 

#include <iostream>
#include <string>
#include <algorithm>
#include <tuple>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std; 
queue <pair <int, int>> q; 
int m, n; 
int map[50][50]; 
int area, area_cnt, area_wall;
int visited[50][50]; 
int dx[4] = { -1,0,1,0 }; 
int dy[4] = { 0,-1,0,1 }; 
int bfs() {
	int a = 0; 
	while (!q.empty()) {
		int y, x; 
		a++; 	
		tie(y, x) = q.front(); 
		q.pop(); 
		for (int i = 0; i < 4; i++) {
			if (map[y][x] &(1 << i))continue; 
			int nx = x + dx[i]; 
			int ny = y + dy[i]; 
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (visited[ny][nx])continue; 
			visited[ny][nx] = 1; 
			q.push({ ny,nx }); 
		}
	}
	return a; 
}
int main() {
	ios::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0); 
	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]) {
				visited[i][j] = 1; 
				area_cnt++; 
				q.push({ i, j });
				area = max(bfs(), area); 
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 4; k++) {
				if (map[i][j] & (1 << k)) {
					memset(visited, 0, sizeof(visited));
					visited[i][j] = 1; 
					map[i][j] ^= (1 << k); 
					q.push({ i,j }); 
					area_wall = max(bfs(), area_wall); 
					map[i][j] |= (1 << k); 
				}
			}
		}
	}	
	cout << area_cnt<<"\n"<<area<<"\n"<<area_wall; 
}

 

2234번: 성곽