[BOJ] 16932번 모양 만들기 (C++)

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

16932번: 모양 만들기

 

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

int n, m;
int arr[1000][1000];
bool visited[1000][1000];
int group[1000][1000];
int group_num = 1;
vector<int> group_size;
int answer = -1;

int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x, y });
	group[x][y] = group_num;
	visited[x][y] = true;
	int cnt = 1;

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

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

			if (arr[nx][ny] == 1 && !visited[nx][ny]) {
				group[nx][ny] = group_num;
				visited[nx][ny] = true;
				q.push({ nx, ny });
				cnt++;
			}
		}
	}
	group_size.push_back(cnt);
	group_num++;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	group_size.push_back(0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 1 && !visited[i][j]) {
				bfs(i, j);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				set<int> group_nums;
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
					if (arr[nx][ny] == 1) {
						group_nums.insert(group[nx][ny]);
					}
				}
				int sum = 1;
				for (int n : group_nums) {
					sum += group_size[n];
				}
				if (sum > answer) answer = sum;
			}
		}
	}

	cout << answer;
	return 0;
}

 

먼저 BFS로 1인 칸의 그룹 번호를 지정해주고, group_size 벡터에 그룹 크기를 저장한다.

 

예제 1번을 예시로 들어보면,

0	1	1
0	0	1
0	1	0

 

다음과 같이 그룹 번호가 지정된다.

0	1	1
0	0	1
0	2	0

 

이 때 group_size[1]은 3, group_size[2]는 1이 된다.

 

 

그룹 번호를 지정한 뒤에, 모든 0에 대하여 해당 칸을 변경했을 때 만들 수 있는 모양의 최대 크기를 구한다.

그럼 모양의 최대 크기를 어떻게 구해야 할까? 0인 칸의 동서남북으로 몇 개의 그룹이 있는지 검사하고(이 때 그룹 번호 중복을 제거하기 위해 set을 쓴다.) 그룹들의 크기 + 1를 하면 된다.

 

예를 들어, 아래의 노란색 0에 대해

0	1	1
0	0	1
0	2	0

 

동서남북으로 4개의 칸을 탐색하면 1, 2 두 개의 그룹이 있으므로 그룹 1의 크기 (3) + 그룹 2의 크기 (1) + 1 = 5를 출력한다.