[백준] 16932 모양 만들기

✔️ 문제 링크

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

16932번: 모양 만들기

---

✔️ 문제 이해

◾ NxM 배열의 각 칸은 0 또는 1로 채워져있다.

◾ 두 칸이 서로 변을 공유할때, 두 칸을 인접한다고 한다. 

◾ 1이 들어 있는 인접한 칸끼리 연결했을때 각 연결 요소를 모양이라고 하고, 모양의 크기는 모양에 포함돼있는 1의 개수다.

◾ 하나의 배열칸 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해야한다. 

---

✔️ 설계

◾ 배열속의 1로 이루어진 각 연결 요소들을 그룹짓고, 각 그룹의 모양 크기를 저장해둔다.

◾ 배열을 순회하며 0인 원소를 기준으로 상하좌우를 확인한다.

◾ 0인 원소를 1로 바꿔보고, 상하좌우에 그룹이 위치하는지 확인한다.

◾ 상하좌우에 그룹이 위치한다면, 해당 그룹의 크기를 더해서 하나의 배열칸 수를 변경해서 만들 수 있는 모양 크기를 구한다.

◾ 매 경우에 최대값 여부를 체크하여 최대값을 구한다. 

---

👨🏻‍💻 소스 코드

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

int n, m;
int map[1000][1000];
int visited[1000][1000];
int group[1000001]; // 그룹은 최대 1000000번까지 존재할 수 있다. 
int groupNum = 1;
int cnt = 0;
int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };

void dfs(int sx, int sy) { // 그룹을 짓기 위한 dfs
	cnt++; // 그룹의 크기를 계산
	visited[sx][sy] = groupNum;

	for (int i = 0; i < 4; i++) {
		int nx = sx + dx[i], ny = sy + dy[i];
		if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
		if (map[nx][ny] == 0) continue;
		if (visited[nx][ny]) continue;
		dfs(nx, ny);
	}
}

void solve() {
	int ret = 0;

	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < m; j++) {
			if (map[i][j] && !visited[i][j]) {
				cnt = 0;
				dfs(i, j); 
				group[groupNum++] = cnt; // 그룹의 크기를 저장.
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {

			if (map[i][j] == 0) { // 0인 원소를 기준으로 상하좌우를 확인.
				int candi = 1; // map[i][j]를 1로 바꿨을때 만들어지는 모양의 크기
				set<int> s; // set으로 이미 포함한 그룹 여부를 확인.
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k], ny = j + dy[k];
					if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
					if (visited[nx][ny] == 0) continue;
					if (s.count(visited[nx][ny])) continue;
					s.insert(visited[nx][ny]);
					candi += group[visited[nx][ny]]; // 최대값 갱신.
				}
				ret = max(ret, candi);
			}

		}
	}
	cout << ret;
}

int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++) { // 배열 입력.
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	solve();
	return 0;
}

---

✔️ 문제 회고

◾ 처음에 모든 경우를 확인하려고 했었다. 하지만 시간복잡도가 O(1000000*1000000)이므로 너무 오래걸렸다.

◾ 그래서 상하좌우에 2개의 1이 존재하는 0에 대해서만 1로 바꾸어 계산해보는 방법을 생각했는데, 이 방법 역시 시간 복잡도가 큰 것은 마찬가지였다. 

◾ 각 모양을 그룹짓고, 그룹의 크기를 따로 저장해둬서 푸는 방법은 시간복잡도가 훨씬 적었다. 

◾ 0을 기준으로 상하좌우에 포함된 그룹의 크기를 더할때, 이미 포함한 그룹에 대한 중복처리를 해줘야했다. 이를 위한 체크 배열 bool check[1000001] = { false }; 을 사용했는데, 이 코드는 1000001번의 연산이 발생한다. 따라서 이중 포문안에 이런 코드를 사용하면, 시간 복잡도가 매우 커졌다. 그래서 set을 사용해서 중복 여부를 판단했다.