[16932번] 모양 만들기

 

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

16932번: 모양 만들기

 

주어진 지도에서 1이 들어있는 칸끼리 연결한 것을 모양이라고 하는데,  지도의 칸에 들어있는 수를 변경해서 모양의 최대 크기를 구하는 문제입니다.

지도는 0, 1로만 구성되어 있는데요. 1을 0으로 바꾸면 모양의 크기는 무조건 줄어들기 때문에 0에서 1로 바꿔는 쪽으로만 생각합니다.

단순히 생각해서 한 칸씩 바뀔 때마다 그룹의 최대 크기를 구해본다고 했을 때, 시간복잡도는 \(O(NM*NM)\)이 나와서 \(1000^4\)이 됩니다. 제한 시간 내 문제를 풀 수 없겠지요.

그래서 해결 방법은 맨 처음에 주어진 지도를 가지고 BFS를 딱 한번만 진행하여 1이 연결되어 있는 그룹들의 번호와 크기를 구해 놓습니다.

그리고 지도에서 0인 칸을 조사하여 인접한 4방향의 값을 체크하여 인접한 칸에 그룹이 존재한다면 그 그룹들의 크기를 더하면 됩니다.

 인접한 그룹의 번호가 동일할 수 있기 때문에 set을 이용하여 한번만 크기를 더해줄 수 있도록 합니다.

 

[코드]

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <set>
using namespace std;
int n, m; //행, 열
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int check[1000][1000];
int a[1000][1000]; //주어진 지도
int group[1000][1000]; //group[i][j] : i행 j열 칸의 그룹번호를 저장
vector<int> gsize; //gsize[i] : 그룹번호가 i인 칸의 개수
void bfs(int sx, int sy) { //칸의 숫자가 1인 곳을 그룹지으면서 각 그룹의 크기를 구합니다.
    int g = gsize.size();//그룹번호를 알아냅니다.
    group[sx][sy] = g; //알아낸 그룹번호를 저장합니다.
    check[sx][sy] = true;
    queue<pair<int, int>> q;
    q.push(make_pair(sx, sy));
    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 (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (a[nx][ny] == 1 && check[nx][ny] == false) {
                    q.push(make_pair(nx, ny));
                    check[nx][ny] = true;
                    group[nx][ny] = g;
                    cnt += 1;
                }
            }
        }
    }
    gsize.push_back(cnt);//현재 그룹의 크기를 저장합니다.
}
int main () {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 1 && check[i][j] == false) {
                bfs(i, j);
            }
        }
    }
    int ans = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 0) { //0인 것을 1로 바꿔보면 그룹의 최대값을 구할 수 있습니다.
                set<int> groupNums; //그룹번호 집합(중복값 불가)
                for (int k = 0; k < 4; k++) {
                    int x, y;
                    x = i + dx[k];
                    y = j + dy[k];
                    if (0 <= x && x < n && 0 <= y && y < m) {
                        if (a[x][y] == 1) { //인접한 칸이 1이라면
                            groupNums.insert(group[x][y]);// 해당 칸의 그룹번호를 set을 이용하여 중복없이 저장합니다.
                        }
                    }
                }
                int sum = 1;
                for (int n : groupNums) {
                    sum += gsize[n]; //그룹 번호에 속해있는 실제 그룹 크기를 합산합니다.
                }
                if (ans == -1 || ans < sum) { //최대값 구하기
                    ans = sum;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

[결과]

5 4 //input
1 1 0 0 //input
1 0 1 0 //input
1 0 1 0 //input
0 1 1 0 //input
1 0 0 1 //input
10 //output