백준2234 - 성곽

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

2234번: 성곽

bfs를 이용하여 푼 문제이다. 문제에서 이진수를 이용하여 풀라고 힌트를 주었다.

 

우선 10진수로 입력 받은 수를 네 자리 이진수로 바꾸어 저장한다. 예를 들어 11이면 1011로 바꾼다는 것이다. 이렇게 바꾼 이진수를 이용하여 1과 0의 위치로 동서남북에 벽이 있는지 찾는다. 네 자리가 나타내는 방향은 남동북서이다.

 

각각의 숫자를 입력 받으면 특정 방에 속하는 칸인지 체크하여 방을 찾는다. bfs를 이용하여 찾고 탐색하는 과정에서 각 방에 속하는 칸인지 세어 특정 변수에 저장한다. bfs를 사용할 때 네 자리수를 각각 한 자리씩 0인지 1인지 비교하여 4방향으로 탐색을 진행한다. 0이면 탐색하고 1이면 탐색하지 않는다. 

 

가장 많은 칸을 차지하는 방은 반복문을 이용하여 탐색하였다. bfs를 이용하여 각 방마다 차지하는 칸의 수를 저장한 공간을 탐색한다.

 

벽을 부수는 작업은 이중포문을 이용하여 풀었다. 각각의 칸에서 4방향으로 현재 있는 칸과 서로 다른 방에 있는 칸인지 비교하여 다르다면 더하는 작업을 통해서 가장 큰 수를 찾았다.

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 51
using namespace std;

int m, n; //가로, 세로
int num; //각 칸의 숫자
int big = -1; //벽을 부수기 전에 가장 큰 넓이
int plus_big = -1; //벽을 부수고 난 후에 가장 큰 넓이
int cnt = 1; //방의 갯수
int d[MAX][MAX] = { 0, }; //각 공간을 탐색한 여부
string mat[MAX][MAX]; //각 칸의 숫자를 이진수로 바꾼 결과를 저장
vector<int> area; //각 방의 넓이를 순서대로 저장

//네 자리 이진수 만들기
string change(int num) {
	string check;
	int len;
	while (num) {
		char temp;
		temp = char('0' + num % 2);
		num = num / 2;
		check = temp + check;
	}
	len = check.size();
	for (int i = 0; i < 4 - len; i++) {
		check = '0' + check;
	}
	return check;
}

void bfs(int x, int y) {
	int res = 1; //현재 탐색하는 곳에 면적
	queue<pair<int, int>> q;
	q.push(pair<int, int>(x, y));
	d[x][y] = cnt;

	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();

		//동서남북으로 벽이 있는지 조사하고 벽이 없으면 탐색한다.
		//탐색할 때 면적을 한 개씩 늘려서 탐색하고 최종적으로 구한 면적을 벡터에 넣는다.
		//탐색할 때 방의 방문 여부는 방의 순서로 기록해 놓아서 bool대신 int를 이용하였다.
		if (mat[x][y][3] == '0') { //west
			if (1 <= x && x <= n && 1 <= y - 1 && y - 1 <= m && !d[x][y - 1]) {
				q.push(pair<int, int>(x, y - 1));
				res++;
				d[x][y - 1] = cnt;
			}
		}
		if (mat[x][y][2] == '0') { //north
			if (1 <= x - 1 && x - 1 <= n && 1 <= y && y <= m && !d[x - 1][y]) {
				q.push(pair<int, int>(x - 1, y));
				res++;
				d[x - 1][y] = cnt;
			}
		}
		if (mat[x][y][1] == '0') { //east
			if (1 <= x && x <= n && 1 <= y + 1 && y + 1 <= m && !d[x][y + 1]) {
				q.push(pair<int, int>(x, y + 1));
				res++;
				d[x][y + 1] = cnt;
			}
		}
		if (mat[x][y][0] == '0') { //south
			if (1 <= x + 1 && x + 1 <= n && 1 <= y && y <= m && !d[x + 1][y]) {
				q.push(pair<int, int>(x + 1, y));
				res++;
				d[x + 1][y] = cnt;
			}
		}
	}
	
	area.push_back(res);
}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> num; //칸에 대한 숫자 입력
			mat[i][j] = change(num); //칸에 대한 숫자를 이진수로 변경하여 저장 
		}
	}

	area.push_back(0); //1번 방부터 시작이여서 0번지를 0으로 채워 놓음
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!d[i][j]) { //탐색을 안한 칸이면 
				bfs(i, j); //같은 방에 있는 칸을 찾아 탐색
				cnt++; //방에 갯수 증가
			}
		}
	}

	//현재 주어진 방 들중 가장 많은 칸을 차지하는 방을 찾음
	for (int i = 1; i < area.size(); i++) {
		big = max(big, area[i]);
	}

	//벽 하나 부수기
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (1 <= i - 1 && i - 1 <= n && 1 <= j && j <= m && d[i - 1][j] != 0 && d[i - 1][j] != d[i][j]) { //유효 범위이고 위에 방이 존재하고 현재 방과 다른 방이면
				plus_big = max(plus_big, area[d[i][j]] + area[d[i - 1][j]]); //현재 벽 부수기 vs 이전 벽 부수기로 큰 값 찾음
			}
			if (1 <= i + 1 && i + 1 <= n && 1 <= j && j <= m && d[i + 1][j] != 0 && d[i + 1][j] != d[i][j]) { //유효 범위이고 아래에 방이 존재하고 현재 방과 다른 방이면
				plus_big = max(plus_big, area[d[i][j]] + area[d[i + 1][j]]); //현재 벽 부수기 vs 이전 벽 부수기로 큰 값 찾음
			}
			if (1 <= i && i <= n && 1 <= j - 1 && j - 1 <= m && d[i][j - 1] != 0 && d[i][j - 1] != d[i][j]) { //유효 범위이고 왼쪽에 방이 존재하고 현재 방과 다른 방이면
				plus_big = max(plus_big, area[d[i][j]] + area[d[i][j - 1]]); //현재 벽 부수기 vs 이전 벽 부수기로 큰 값 찾음
			}
			if (1 <= i && i <= n && 1 <= j + 1 && j + 1 <= m && d[i][j + 1] != 0 && d[i][j + 1] != d[i][j]) { //유효 범위이고 오른쪽에 방이 존재하고 현재 방과 다른 방이면
				plus_big = max(plus_big, area[d[i][j]] + area[d[i][j + 1]]); //현재 벽 부수기 vs 이전 벽 부수기로 큰 값 찾음
			}
		}
	}

	cout << cnt - 1 << '\n';
	cout << big << '\n';
	cout << plus_big;
}