(C++) - 백준(BOJ) 2234 : 성곽

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

2234번: 성곽

bitmasking을 이용한 bfs문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 n행 m열

 벽의 정보를 저장할 2차원 배열 wall

 방문 여부를 확인할 이차원 배열 ck

 방의 개수를 저장할 roomCnt

 가장 넓은 방의 크기를 저장할 biggestRoomSize

 벽 하나를 허물었을 때 구할 수 있는 가장 넓은 방의 크기 biggestRoomSize2를 선언하고 입력받습니다.

 

📔 풀이과정

구해야 하는 답은 3가지입니다.

 

 1) 이 성에 있는 방의 개수

 2) 가장 넓은 방의 넓이

 3) 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

 

 1), 2)구하기 :  방문 하지 않은 칸은 새로운 방입니다. 따라서 roomCnt++ 후 bfs를 수행해서 해당 방의 넓이를 반환해줍니다. bfs의 반환값은 biggestRoomSize과 비교해 최댓값을 biggestRoomSize에 저장해줍니다.

 3)구하기 :  벽을 하나씩 허물고 bfs를 호출한뒤 최댓값을 허문 벽을 원복해줍니다. 마찬가지로 수행한 뒤 최댓값을 biggestRoomSize2에 저장해줍니다.

 

bfs수행시 여러가지를 고려해야합니다.

1. 이미 방문한 칸은 중복해서 방문하면 안됩니다.

2. 상하좌우를 확인하며 방 범위를 넘어갈 수 있으니 접근하지 않도록 if문으로 경계를 정해줍니다. 

3. bitmasking으로 벽이 어느방향에 존재하는지 알 수 있습니다. 동, 서, 남, 북 4방향에 대해 &연산으로

wall[r][c] & 방향을 수행해 자기 자신이 나오는 경우 그 방향에는 벽이 있음을 O(1)로 알 수 있습니다.

📔 정답출력

roomCnt, biggestRoomSize, biggestRoomSize2를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair <int,int>;
int n, m, wall[51][51], ck[51][51], roomCnt, biggestRoomSize, biggestRoomSize2;
int dr[] = {0, -1, 0, 1};
int dc[] = {-1, 0, 1, 0};
int bfs(int i, int j){
    int roomSize = 1;
    ck[i][j] = 1;
    queue <pii> q;
    q.push({i, j});
    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        int wallInfo = wall[r][c];
        for(int dir = 0; dir < 4; dir++){
            int nr = r + dr[dir];
            int nc = c + dc[dir];
            if(0 > nr || nr >= n || 0 > nc || nc >= m) continue;
            //벽있다면 continue;
            if((wallInfo & (1 << dir)) || ck[nr][nc]) continue;
            roomSize++;
            q.push({nr, nc});
            ck[nr][nc] = 1;
        }
    }
    return roomSize;
}

int main(){
    cin >> m >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> wall[i][j];

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!ck[i][j]){
                biggestRoomSize = max(biggestRoomSize, bfs(i, j));
                roomCnt++;
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(int dir = 1; dir <= 8; dir <<= 1){
                if(wall[i][j] & dir){
                    memset(ck, 0, sizeof(ck));
                    wall[i][j] -= dir;
                    biggestRoomSize2 = max(biggestRoomSize2, bfs(i, j));
                    wall[i][j] += dir;
                }
            }
        }
    }

    cout << roomCnt << '\n' << biggestRoomSize << '\n' << biggestRoomSize2 << '\n';
}