[BOJ] 2234 성곽

문제보기

1.10진수를 4비트 2진수로 변경

2.BFS로 뚫려있는 부분만 큐에 넣어 방 도출해서 각 방에 번호 붙임 

=> 방의 갯수, 가장 넓은 방 넓이

3.0,0부터 오른쪽 아래까지 현재 좌표에서 오른쪽, 아래쪽을 검사 하면서 

방번호가 다르면 두 방의 넓이를 더한것 중 가장 큰것

=>하나의 벽을 제거해서 얻을 수 있는 가장 넓은 방의 크기

---

#include <queue>

#include <algorithm>

using namespace std;

int dy[4] ={1,0,-1,0};

int dx[4] ={0,1,0,-1};

int map[51][51]={0};

int check[51][51]={0};

int N,M;

int checkNum = 1;

int* getBinary(int n){

static int tp[4];

for(int i = 0;i<4;i++){

tp[i] = 0;

}

int i = 3;

while(true){

if(n%2)

tp[i--] = 1;

else

tp[i--] = 0;

n /= 2;

if(n == 0){

break;

}

}

return tp;

}

int BFS(int y,int x){

int *wall;

queue<pair<int,int > > q;

int roomSize = 0;

q.push(make_pair(y,x));

while(!q.empty()){

int y = q.front().first;

int x = q.front().second;

wall = getBinary(map[y][x]);

q.pop();

check[y][x] = checkNum;

for(int i = 0;i<4;i++){

if(wall[i] == 0){

int nx = x + dx[i];

int ny = y + dy[i];

if(nx >=0 && nx <= N-1 && ny >=0 && ny <=M-1){

if(check[ny][nx] == 0){

q.push(make_pair(ny,nx));

check[ny][nx] = checkNum;

}

}

}

}

roomSize++;

}

return roomSize;

}

int main(){

int roomSizes[2502]={};

scanf("%d%d",&N,&M);

for(int i = 0;i<M;i++){

for(int j = 0;j<N;j++){

scanf("%d",&map[i][j]);

}

}

int numOfRoom = 0;

int maxRoomSize = 0;

for(int i = 0;i<M;i++){

for(int j = 0;j<N;j++){

if(check[i][j] == 0){

roomSizes[checkNum] = BFS(i,j);

maxRoomSize = max(maxRoomSize,roomSizes[checkNum++]);

numOfRoom++;

}

}

}

int maxRoomSize2 = 0;

for(int i = 0;i<M;i++){

for(int j = 0;j<N;j++){

if(i+1<M && check[i][j] != check[i+1][j]){

int sum = roomSizes[check[i][j]] + roomSizes[check[i+1][j]];

maxRoomSize2 = max(maxRoomSize2,sum);

}

if(j+1<N &&check[i][j] != check[i][j+1]){

int sum = roomSizes[check[i][j]] + roomSizes[check[i][j+1]];

maxRoomSize2 = max(maxRoomSize2,sum);

}

}

}

printf("%d\n",numOfRoom);

printf("%d\n",maxRoomSize);

printf("%d\n",maxRoomSize2);

}