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

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

2234번: 성곽

 

1. 접근

요구하는게 많았는데 일단 유니온파인드로 푸는 문제인줄 알았지만 bfs로 푸는 문제

 

2. 핵심

1) 벽 유무를 비트마스킹을 통해 연산(나는 처음에 map[y][x] 값 받자마자 소인수분해로 map[y][x][4] 값을 채웠다)

2) 아래 코드에선 개선하지 않았는데 3번째 요구사항인 벽을 부쉈을 때의 방크기 최대값은 bfs()에서 방 넘버링을 하면 시간을 더 줄일 수 있을 것 같다

 

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;


int n, m, map[50][50];
bool chk[50][50] = { false, };
pair<int, int> dir[4] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} }; // 서, 북, 동, 남
int cnt = 0, area = 0, mArea = 0;

int bfs(int y, int x) {
	int cArea = 0;
	queue<pair<int, int>> q;
	q.push({ y,x });
	chk[y][x] = true;
	cArea++;

	while (!q.empty()) {
		int cy = q.front().first, cx = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + dir[i].first, nx = cx + dir[i].second;

			if (ny<0 || ny>m || nx<0 || nx>n || chk[ny][nx] || map[cy][cx] & (1 << i))
				continue;

			q.push({ ny,nx });
			chk[ny][nx] = true;
			cArea++;
		}
	}

	return cArea;
}

int main() {

	ios::sync_with_stdio(0);
	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 (!chk[i][j]) {
				area = max(area, bfs(i, j));
				cnt++;
			}
		}
	}

	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 4; k++) {
				int by = i + dir[k].first, bx = j + dir[k].second;

				if (by >= 0 && by < m&&bx >= 0 && bx < n && (map[i][j] & (1 << k))) {
					for (int p = 0; p < m; p++)
						for (int q = 0; q < n; q++)
							chk[p][q] = false;
					
					map[i][j] -= (1 << k);
					mArea = max(mArea, bfs(i, j));
					map[i][j] += (1 << k);
				}
			}
		}
	}

	cout << cnt << "\n" << area << "\n" << mArea << "\n";

	return 0;
}