[백준] 2234 성곽

문제

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

출력

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

 

각 칸에 둘러싸인 벽의 정보를 정수로 입력받습니다.

이 정수를 2진수로 바꾸면..

15 >> 1 1 1 1

10 >> 1 0 1 0

이렇게 바꿀 수 있습니다. 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { 0,-1,0,1 }, dx[] = { -1,0,1,0 };
int N, M, mp[51][51], v[51][51], cnt, ans =2, num, n[2501];
void dfs(int y, int x) {
	v[y][x] = cnt;
	num++;
	rep(i, 4) {
		if (((1 << i) & ~mp[y][x]) && !v[y+dy[i]][x+dx[i]]) {
			dfs(y+dy[i], x+dx[i]);
		}
	}
}
void check(int y, int x) {
	rep(i, 4) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 0 && ny < N && nx >= 0 && nx < M) {
			if (v[y][x] != v[ny][nx]) {
				ans = max(ans, n[v[y][x]] + n[v[ny][nx]]);
			}
		}
	}
}
int main() {
	FAST;
	cin >> M >> N;
	rep(i, N)rep(j, M)cin >> mp[i][j];

	rep(i, N)rep(j, M)if (!v[i][j]) {
		++cnt;
		dfs(i, j);
		n[cnt] = num;
		num = 0;
	}
	rep(i, N)rep(j, M)check(i, j);
	cout << cnt << "\n" << *max_element(n + 1, n + 1 + cnt) << "\n" << ans;
}

 

void dfs(int y, int x) {
	v[y][x] = cnt;
	num++;
	rep(i, 4) {
		if (((1 << i) & ~mp[y][x]) && !v[y+dy[i]][x+dx[i]]) {
			dfs(y+dy[i], x+dx[i]);
		}
	}
}

서,북,동,남 4방향을 기준으로 벽이 있는지 없는지 확인합니다.

비트마스킹을 사용합니다

1<<0 : 1 이므로 서쪽에 벽이 있는지 확인합니다

1<<1 : 2 북

1<<2 : 4 동

1<<8 : 8 남

1<<i & ~mp[y][x]를 사용하면 i방향에 벽이 있는지 없는지 확인하고, 벽이 없다면 dfs를 수행합니다.