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

 

 

문제

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.

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

배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

출력

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

 

접근 방식

 

처음에는 모든 0 요소에 대해 BFS를 반복하면서 최대 크기를 찾으려고 했다.

하지만 그렇게 하니 시간초과가 발생하였고

 

두번째로 생각한 방식은

1로 연결된 모든 모양의 크기를 모두 구한 다음,

0 요소를 찾으면서 연결된 1 모양의 크기를 더해서 최대 크기를 만드는 방식이다.

 

3 3
0 1 1
0 0 1
0 1 0

 

즉, 위와 같은 테스트 케이스가 있을 때

 

0 3 3
0 * 3
0 1 *

 

*위치에 있는 0들은 3+1+1로 최대 크기 5를 가질 수 있게 된다.

 

하지만, 여기서 문제였던 것은

BFS를 탐색하면서 연결된 사이즈로 1을 바꿔줘야 하는 것이였다.

 

따라서, 각 모양마다 id를 부여하고

각 id에 따라 사이즈를 저장하는 배열을 따로 생성해주었다.

 

또한, 1로 바꿀 0을 찾는 과정에서

같은 id를 가진 영역이 중복으로 더해질 수 있으므로

set을 사용해 중복값을 없애주었다.

 

간단하면서도 생각할 거리가 많은 문제였다.

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int N,M, ans = 0;
int mat[1002][1002], area_size[10000002], area_id[1002][1002];
bool visited[1002][1002];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int id = 1;

void BFS(int i, int j) {
    queue<tuple<int,int>> q;
    q.push({i,j});
    visited[i][j] = true;
    area_id[i][j] = id;
    int size = 0;

    while(!q.empty()) {
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        q.pop();
        size++;
        

        for(int r=0; r<4; r++) {
            int nx = x + dx[r];
            int ny = y + dy[r];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny] || mat[nx][ny] == 0) continue;
            q.push({nx,ny});
            visited[nx][ny] = true;
            area_id[nx][ny] = id;
        }
    }
    area_size[id] = size;
    id++;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>N>>M;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin>>mat[i][j];
        }
    }

    memset(visited, false, sizeof(visited));

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(mat[i][j] == 1 && !visited[i][j]) {
                BFS(i,j);
            }
        }
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(mat[i][j] == 0) {
                set<int> s;
                int new_size = 1;

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

                    if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                    if(mat[nx][ny] == 1) s.insert(area_id[nx][ny]);
                }

                for(int id : s) new_size += area_size[id];

                ans = max(ans, new_size);
            }
        }
    }



    cout<<ans;

}