[C++] 백준 2234 - 성곽

2234번: 성곽

---

풀이

비트연산자를 이용해서 방 구역 나누기 > 각 방 넓이 구하기 > 방 합치기 순으로 진행해서 풀었다.

 

 

 

코드

#include <bits/stdc++.h>

using namespace std;

int board[51][51];
int room[51][51];
int roomArea[2505];
int roomNum = 1;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int answer = 10000000;
int h,w;
int maxArea = 0;
bool InMap(int x,int y){
    if(0 <= x && x < w && 0<= y && y < h)
    return true;
    return false;
}
int RoomSet(int x,int y){
    if(room[y][x] != 0)
    return 0;
    
    queue<pair<int,int>> q;
    q.push(make_pair(x,y));
    while(!q.empty()){
        int xx = q.front().first;
        int yy = q.front().second;
        q.pop();
        if(!InMap(xx, yy))
        continue;
        
        if(room[yy][xx] != 0)
        continue;
        
        room[yy][xx] = roomNum;
        roomArea[roomNum]++;
        int wall = board[yy][xx];
        // 서쪽
        if((wall & 1)==0){
            q.push(make_pair(xx-1,yy));
        }
        // 북
        if((wall & 2)==0){
            q.push(make_pair(xx,yy-1));
        }
        // 동
        if((wall & 4)==0){
            q.push(make_pair(xx+1,yy));
        }
        // 남
        if((wall & 8)==0){
            q.push(make_pair(xx,yy+1));
        }
    }
    roomNum++;
    return roomArea[roomNum-1];
}

void SumRoom(int x,int y){
    int nowRoom = room[y][x];
    int nowArea = roomArea[nowRoom];
    int wall = board[y][x];
    // 서쪽뚫기
    if((wall & 1)==1){
        // 맵 안이고 같은 방아니면
        if(InMap(x-1, y)){
            int nextRoom = room[y][x-1];
            int nextArea = roomArea[nextRoom];
            if(nowRoom != nextRoom){
               maxArea = max(maxArea, nowArea + nextArea); 
            }
        }
    }
        // 북
    if((wall & 2)==2){
        if(InMap(x, y-1)){
            int nextRoom = room[y-1][x];
            int nextArea = roomArea[nextRoom];
            if(nowRoom != nextRoom){
               maxArea = max(maxArea, nowArea + nextArea); 
            }
        }
        
    }
        // 동
    if((wall & 4)==4){
        if(InMap(x+1, y)){
            int nextRoom = room[y][x+1];
            int nextArea = roomArea[nextRoom];
            if(nowRoom != nextRoom){
               maxArea = max(maxArea, nowArea + nextArea); 
            }
        }
    }
        // 남
    if((wall & 8)==8){
        if(InMap(x, y+1)){
            int nextRoom = room[y+1][x];
            int nextArea = roomArea[nextRoom];
            if(nowRoom != nextRoom){
               maxArea = max(maxArea, nowArea + nextArea); 
            }
        }
    }
}
int main()
{
    int maxRoom = 0;
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> w >> h;
    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            cin >> board[y][x];
        }
    }
    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            maxRoom = max(maxRoom,RoomSet(x,y));
        }
    }
    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            SumRoom(x,y);
        }
    }
    cout << roomNum-1 << endl;
    cout << maxRoom << endl;
    cout << maxArea;
    return 0;
}