[백준 16932번] 모양 만들기

문제 링크: https://www.acmicpc.net/problem/16932

16932번: 모양 만들기

<문제 풀이> BFS

1. 1로 이루어진 연결 요소를 구해서 그룹화한다.

-> 그룹화는 각각의 연결 요소에 번호를 부여

 

2. 배열에서 0을 찾아서 (상하좌우 영역의 크기 + 1 ( 0을 1로 바꾼 경우))의 최댓값을 구한다.

-> 이때 같은 상하좌우를 확인할 때 같은 영역은 중복 체크하지 않도록 check 배열을 하나 둬야 한다.

<C++ 소스 코드>

#include<iostream>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;
 
#define X first
#define Y second
 
int N, M;
 
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
 
 
int board[1000][1000];
bool visited[1000][1000];
bool check[1000000];
int area[1000000];
int res = 0;
int num = 1;
 
int dfs(int cx, int cy) {
    int ret = 1;
    for (int dir = 0; dir < 4; dir++) {
        int nx = cx + dx[dir];
        int ny = cy + dy[dir];
        if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
        if (board[nx][ny] != 0 && !visited[nx][ny]) {
            board[nx][ny] = num;
            visited[nx][ny] = true;
            ret += dfs(nx, ny);
        }
    }
    return ret;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 1 && !visited[i][j]) {
                visited[i][j] = true;
                board[i][j] = num;
                area[num] = dfs(i, j);
                num++;
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 0) {
                int temp = 1;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
                    if (board[nx][ny] != 0 && !check[board[nx][ny]]){
                        temp += area[board[nx][ny]];
                        check[board[nx][ny]] = true;
                    }
                    
                }
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
                    if (board[nx][ny] != 0) {
                        check[board[nx][ny]] = false;
                    }
 
                };
                res = max(res, temp);
            }
        }
    }
    cout << res;
    return 0;
}