(c++)백준 2234번: 성곽

www.acmicpc.net/problem/2234

2234번: 성곽

[풀이]

문제 풀이에 대한 감을 못 잡아서 결국 다른 분의 풀이를 참고했다.

&연산을 사용하여 벽의 유무를 알아내야 하는 문제였다.

 

Map[i][j] & 1 = 0001이면 (i,j)칸의 서쪽에 벽이 있다는 뜻이다.

마찬가지로, Map[i][j] & 2 = 0010이면 북쪽에 벽이,

Map[i][j] & 4 = 0100이면 동쪽에 벽이,

Map[i][j] & 8 = 1000이면 남쪽에 벽이 있다는 뜻이다.

 

구할 것

1. 이 성에 있는 방의 개수

→bfs 호출 횟수로 구할 수 있다.

2. 가장 넓은 방의 넓이

→아직 방문하지 않은 칸을 방문할 때 cnt++하고 탐색을 마치면 cnt를 반환하여 구할 수 있다.

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

→존재하는 벽을 하나씩 다 없애보면 된다. 해당 칸의 값과 1,2,4,8을 &연산하여 벽이 있으면 그 값을 빼고 bfs실행하여 방의 크기를 구할 수 있다.

 

움직일 수 있는 조건

-벽이 없어야 됨

-4방향 탐색할 때 벽의 유무도 같이 탐색!

→성의 해당 칸의 값과 1,2,4,8 &연산 

 

#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;

struct Pos {
	int x, y;
};

int n, m;
int Map[50][50];
bool visited[50][50];
const int dx[] = { 0,-1,0,1 };//서, 북, 동, 남
const int dy[] = { -1,0,1,0 };//1,2,4,8 순서!

int bfs(int startx, int starty) {
	int room_size = 1;
	queue<Pos>q;
	q.push({ startx,starty });
	visited[startx][starty] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		int wall = 1;
		for (int i = 0; i < 4; i++) {
			//해당 방향에 벽이 없으면
			if ((Map[x][y] & wall) != wall) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= m || ny < 0 || ny >= n)
					continue;
				if (visited[nx][ny] == false) {
					visited[nx][ny] = true;
					q.push({ nx,ny });
					room_size++;
				}
			}
			wall = wall * 2;
		}
	}
	return room_size;
}

int main() {
	cin >> n >> m;
	int room_cnt = 0;
	int largest_room = -1;
	int largest_room2 = -1;
	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] == false) {
				int room_size = bfs(i, j);
				if (largest_room < room_size)
					largest_room = room_size;
				room_cnt++;
			}
		}
	}
	
	//하나의 벽 제거하여 얻을 수 있는 가장 넓은 방의 크기 구하기
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			for (int wall = 1; wall <= 8; wall *= 2) {
				if ((Map[i][j] & wall) == wall) {
					memset(visited, false, sizeof(visited));
					Map[i][j] -= wall;
					int room_size = bfs(i, j);
					if (largest_room2 < room_size)
						largest_room2 = room_size;
					Map[i][j] += wall;
				}
			}
		}
	}
	cout << room_cnt << '\n' << largest_room << '\n' << largest_room2 << '\n';
	return 0;
}