BOJ_2234 : 성곽

문제링크

문제 풀어보기

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <queue>

using namespace std;
int n, m;
int arr[55][55];
int room[55][55];


int dx[] = {  0, -1 ,0, 1 };
int dy[] = {  -1, 0, 1, 0 };
// 서 북 동 남

int bfs(int a, int b, int index) {
	queue< pair<int, int> > q;
	room[a][b] = index;
	q.push(make_pair(a, b));
	int cnt = 1;
	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (arr[x][y] & (1 << k)) continue;
			if (room[nx][ny] != 0) continue;
			room[nx][ny] = index;
			q.push(make_pair(nx, ny));
			cnt++;
		}
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> m >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	vector<int> room_sz(50 * 50, 0);
	int index = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (room[i][j] != 0) continue;
			index++;
			room_sz[index] = bfs(i, j, index);
		}
	}
	cout << index  << '\n';

	cout << *max_element(room_sz.begin(), room_sz.end()) << '\n';

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (room[i][j] == room[nx][ny]) continue;
				if (arr[i][j] & (1 << k)) {
					int maxx = room_sz[room[i][j]] + room_sz[room[nx][ny]];
					if (ans < maxx) ans = maxx;
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;
}