[BAE/<JOON> 문제풀이] 2234. 성곽

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

2234번: 성곽

서론

Flood-Fill BFS 문제

---

풀이

이 문제는 특이하게 cell 마다 4개의 벽이 있을 수 있고 벽의 상태를 2진수로 저장했다.

총 3가지를 구해야 한다.

1. 방의 개수 = BFS 

2. 가장 넓은 방의 넓이 = BFS

3. 하나의 벽을 제거해 얻을 수 있는 가장 넓은 방의 크기 = 인접한 2개의 방의 합의 최대 크기

 

3번은 각 방에 해당하는 cell들을 배열로 저장한 뒤 순회하며 어떤 cell 의 벽 너머에 현재 방과 다른 방이 있을 때 그 넓이의 합을 구하고 최대값을 갱신했다. 이 때, 벽 너머라고 해도 같은 방일 수 도 있으므로 반드시 방번호를 검사해야한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <cstdlib>
using namespace std;
const long long mod = 10e8 + 7;
using ll = long long;
struct fi {
	int i, d, die = 0;
};
struct co {
	int x, y;
};
struct pos {
	int x, y, cnt;
};
struct cmp {
	bool operator() (pos a, pos b) {
		return a.cnt > b.cnt;
	}
};
int mvx8[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int mvy8[8] = { -1 ,-1, 0, 1, 1, 1, 0, -1 }; 
int mvx4[4] = { 0, -1, 0, 1 };
int mvy4[4] = { -1, 0, 1, 0 };
struct st {
	int a, b, c;
};

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> m >> n; vector<vector<int>> arr(n + 1, vector<int>(m + 1)), room(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}	
	int rc = 0; vector<vector<pos>> rl; int msz = 0; int psz = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (room[i][j] == 0) {
				vector<pos> rp; rp.push_back({ i, j });
				room[i][j] = ++rc;
				queue<pos> q; q.push({ i, j, 0 });
				while (!q.empty()) {
					auto cur = q.front(); q.pop();
					for (int k = 0; k < 4; k++) {
						if ((arr[cur.x][cur.y] & (1 << k)) == 0) {
							int mx = cur.x + mvx4[k];
							int my = cur.y + mvy4[k];
							if (mx > n || my > m || mx < 1 || my < 1 || room[mx][my] != 0) continue;
							room[mx][my] = rc;
							q.push({ mx, my, 0 });
							rp.push_back({ mx, my });
						}
					}
				}
				msz = rp.size() > msz ? rp.size() : msz;
				rl.push_back(rp);
			}
		}
	}
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << room[i][j] << " ";
		}
		cout << "\n";
	}*/
	int mx = 0;
	for (auto r : rl) {
		vector<int> ch(rl.size());
		for (const auto& c : r) {			
			for (int k = 0; k < 4; k++) {
				int mx = c.x + mvx4[k];
				int my = c.y + mvy4[k];
				if (mx > n || my > m || mx < 1 || my < 1) continue;
				if ((arr[c.x][c.y] & (1 << k)) > 0 && ch[room[mx][my] - 1] == 0 && room[mx][my] != room[c.x][c.y]) {
					ch[room[mx][my] - 1] = 1;
					int ps = r.size() + rl[room[mx][my] - 1].size();
					psz = psz > ps ? psz : ps;
				}
			}
		}
	}
	cout << rl.size() << "\n";
	cout << msz << "\n";
	cout << psz << "\n";
	return 0;
}