BOJ) 2234 - 성곽

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

2234번: 성곽

4자리 bitset을 이용해서 풀이했습니다.

벽에 대한 정보가 입력될 때마다 k번째 자릿수가 포함되어 있는지 map배열에 체크해줍니다.

ex ) 11은 2진수로 1011  => 1,2,4자릿수가 포함되어 있음 => 서,북,남쪽으로 벽이 있는 칸

 

map에 저장한 벽 정보를 바탕으로 dfs를 수행하며 각 칸의 방 번호 (visit 배열 )와  방의 크기 (roomIdx 배열) 를 저장해줍니다.

visit배열에 저장한 각 칸의 방번호를 이용해 2중 for문을 수행하여, 인접한 다른 방을 합쳐보며 가장 큰 경우를 구합니다

---

C++ 소스 코드

#include <cstdio>
#include <bitset>
using namespace std;
int map[51][51][4]; // (x,y) 칸의 벽 정보 저장
int a[51][51];
const int dx[]= {0,-1,0,1}, dy[]={-1,0,1,0}; // 서,북,동,남 시계방향 순
int n,m,roomcnt,mxroomsize,removemx,cnt;
int visit[51][51]; // 각 칸에 방번호 저장
int roomidx[51]; // 각 방의 크기 저장
void dfs(int x, int y){
    cnt++;
    visit[x][y]=roomcnt;
    for(int i=0;i<4;i++){
        //이동하려는 방향으로 벽이 있는지 체크
        if (map[x][y][i]) continue;
        int nx = x+dx[i], ny= y +dy[i];
        if(nx <0 || nx >=n || ny <0 || ny>= m ||visit[nx][ny]) continue;
        dfs(nx,ny);
    }
}
int main(){
    scanf("%d %d", &m, &n);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            bitset<4> bits;
            scanf("%d",&a[i][j]);
            bits = a[i][j];
            if(bits[3]) map[i][j][3]=true;
            if(bits[2]) map[i][j][2]=true;
            if(bits[1]) map[i][j][1]=true;
            if(bits[0]) map[i][j][0]=true;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visit[i][j]){
                roomcnt++;
                dfs(i,j);
                if(cnt > mxroomsize) mxroomsize = cnt;
                roomidx[roomcnt]=cnt;
                cnt=0;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<4;k++){
                int nx = i+dx[k], ny = j+dy[k];
                if (nx <0|| nx >=n || ny <0 || ny >=m) continue;
                if(visit[i][j]==visit[nx][ny]) continue;
                if(roomidx[visit[i][j]]+roomidx[visit[nx][ny]]>removemx) {
                    removemx = roomidx[visit[i][j]]+roomidx[visit[nx][ny]];
                }
            }
        }
    }
    printf("%d\n%d\n%d\n",roomcnt,mxroomsize,removemx);
    return 0;
}