[백준 16932] 모양 만들기, C++

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

16932번: 모양 만들기

 본 문제는 0을 1로 바꿨을 때, 인접한 칸의 1의 개수가 최대인 크기를 구하는 문제다. 입력의 크기가 최대 1,000이므로 입력된 배열의 전체를 탐색하면서 0을 1로 바꾸고, 1의 개수를 확인하면 시간초과가 나온다. 따라서, 다른 방법으로 문제해결을 해야한다.

1. bfs로 전체 탐색하여 인접한 1의 그룹을 나눈다.
2. 전체 탐색을 하면서 0일 때, 인접한 칸이 1인지 확인
3. 1일 경우 해당 그룹의 개수를 더한다.
   • 이때, 그룹의 중복이 있을 수 있으니, 중복된 그룹은 제거한다.
4. 만들 수 있는 모든 경우를 확인하면서 최댓값을 찾는다.

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int d[1001][1001];
int a[1001*1001];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m;
bool chk[1001][1001];
bool c[1001];
 
int main() {
    scanf("%d %d", &n ,&m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &d[i][j]);
        }
    }
    queue<pair<int, int>> q;
    int cal = 0;
    // bfs 탐색
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!chk[i][j] && d[i][j] == 1) {
                cal += 1;
                q.push(make_pair(i, j));
                chk[i][j] = true;
                d[i][j] = cal;
                int cnt = 1;
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    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) {
                            if (!chk[nx][ny] && d[nx][ny] == 1) {
                                cnt += 1;
                                d[nx][ny] = cal;
                                chk[nx][ny] = true;
                                q.push(make_pair(nx, ny));
                            }
                        }
                    }
                }
                a[cal] = cnt;
            }
        }
    }
    vector<int> ans;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            if (d[x][y] == 0) {
                vector<int> add;
                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) {
                        // 인접하 칸이 1일 경우 (0이 아닐 경우)
                        if (d[nx][ny] != 0) {
                            add.push_back(d[nx][ny]);
                        }
                    }
                }
                // 중복값 제거
                sort(add.begin(), add.end());
                add.erase(unique(add.begin(), add.end()), add.end());
                int result = 0;
                // 최댓값 탐색
                for (int k = 0; k < add.size(); k++) {
                    result += a[add[k]];
                }
                ans.push_back(result);
            }
        }
    }
    sort(ans.rbegin(), ans.rend());
    printf("%d\n", ans[0]+1);
}