(C++) - 백준(BOJ) 16932번 : 모양 만들기

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

16932번: 모양 만들기

아이디어가 필요한 bfs였습니다.

 

📕 풀이방법

📔 입력 및 초기화

n(행), m(열), groupNum(그룹번호), groupCk(그룹 체크 배열), board(입력받을 2차원 배열), ck(board 방문여부 확인 배열) dr,dc(인접 4방향 확인용 배열), areaPerGroup(그룹당 영역을 의미하는 unordered_map)을 선언합니다.n행, m열 입력 후 board에 n x m만큼 입력받습니다.

 

 

📔 풀이과정

 1. 그룹 정하기 : n X m 만큼 loop를 돌며 방문한 적 없으며 새로운 그룹을 발견했다면 이를 시작점으로해 group 번호를 bfs를 통해 부여합니다.

 

 2. 모양 크기 구하기 : board의 i행 j열이 0인 경우 다음을 수행합니다.   2-1. i,j가 0이라면 이를 기점으로 인접한 칸이 방문하지 않은 그룹인지 확인해줍니다.  2-2. 방문하지 않은 그룹이라면 이제 i,j의 모양을 바꾼다고 생각합니다. 인접 칸에 해당하는 그룹에 방문표시를 해주고 해당 그룹의 모양 크기를 cnt변수에 더해줍니다. 

  2-3. cnt는 i,j를 1로 바꿔줬을 때 연결된 한 모양의 크기입니다. cnt를 구했으니 체크해줬던 그룹들을 해제해줍니다. 다음에 그 그룹들은 다시 사용될 수 있기 때문입니다.

 2-4 cnt와 ans의 최댓값을 ans에 저장합니다.

 

📔 정답출력

ans를 출력합니다.

---

 

 📕 Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
int n, m, ans, groupNum, groupCk[100001];
int board[1001][1001], ck[1001][1001];
int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};
unordered_map <int, int> areaPerGroup;

void paintArea(int i, int j){
    groupNum++;
    ck[i][j] = 1;
    queue <pii> q;
    q.push({i, j});
    int cnt = 1;
    board[i][j] = groupNum;

    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(0 > nr || nr >= n || 0 > nc || nc >= m) continue;
            if(!board[nr][nc] || ck[nr][nc]) continue;
            board[nr][nc] = groupNum;
            ck[nr][nc] = 1;
            cnt++;
            q.push({nr, nc});
        }
    }

    areaPerGroup[groupNum] = cnt;
}

int main(){
    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] && !ck[i][j])
                //새로운 영역
                paintArea(i, j);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(board[i][j]) continue;

            int cnt = 1;

            for(int d = 0; d < 4; d++){
                int nr = i + dr[d];
                int nc = j + dc[d];
                if(board[nr][nc] && !groupCk[board[nr][nc]]){
                    groupCk[board[nr][nc]] = 1;
                    cnt += areaPerGroup[board[nr][nc]];
                }
            }

            for(int d = 0; d < 4; d++){
                int nr = i + dr[d];
                int nc = j + dc[d];
                groupCk[board[nr][nc]] = 0;
            }

            ans = max(ans, cnt);
        }
    }
    
    cout << ans;
}