[BOJ] 2234 성곽 C++

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

2234번: 성곽

전형적인 DFS,BFS 문제이다. 까다로운 점이 있다면 비트마스킹을 사용해야 한다는 점인데 아마 비트 마스킹을 공부 했던 분들이라면 쉽게 풀 수 있을 것이라고 생각한다.

한가지 더 어려운 점이 있다면 벽 하나를 뚫었을 때 가장 큰 방의 크기를 구하는 문제였는데 나는 모든 방에 색깔 정보와 해당 색깔의 방을 크기를 저장하였다. 모든 방을 방문하면서 상하좌우의 방과 색깔이 다를 경우 두 색깔의 방의 크기를 더한 값 중 최댓값을 출력해주었다.

 

코드

#include <iostream>
using namespace std;
int N,M;
int map_info[50][50];
int map_color[50][50];
int size_info[2501];
int ans1=0,ans2=0,ans3=0;

int DFS(int i,int j,int n){
    map_color[i][j]=n;
    int cnt=1;
    if(!(1&map_info[i][j])){
       if(map_color[i][j-1]==0){
           cnt+=DFS(i,j-1,n);
       }
    }
    if(!(2&map_info[i][j])){
       if(map_color[i-1][j]==0){
           cnt+=DFS(i-1,j,n);
       }
    }
    if(!(4&map_info[i][j])){
       if(map_color[i][j+1]==0){
           cnt+=DFS(i,j+1,n);
       }
    }
    if(!(8&map_info[i][j])){
       if(map_color[i+1][j]==0){
           cnt+=DFS(i+1,j,n);
       }
    }
    return cnt;
}

int main(){
    cin>>N>>M;
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++) cin>>map_info[i][j];
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            if(map_color[i][j]==0){
                ans1++;
                size_info[ans1]=DFS(i,j,ans1);
                ans2=max(size_info[ans1],ans2);
            }
        }
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            if(i+1<M&&(map_color[i][j]!=map_color[i+1][j])){
                ans3=max(ans3,size_info[map_color[i][j]]+size_info[map_color[i+1][j]]);
            }
            if(i-1>0&&(map_color[i][j]!=map_color[i-1][j])){
                ans3=max(ans3,size_info[map_color[i][j]]+size_info[map_color[i-1][j]]);
            }
            if(j+1<N&&(map_color[i][j]!=map_color[i][j+1])){
                ans3=max(ans3,size_info[map_color[i][j]]+size_info[map_color[i][j+1]]);
            }
            if(j-1>0&&(map_color[i][j]!=map_color[i][j-1])){
                ans3=max(ans3,size_info[map_color[i][j]]+size_info[map_color[i][j-1]]);
            }
        }
    }
    cout<<ans1<<'\n';
    cout<<ans2<<'\n';
    cout<<ans3<<'\n';
    return 0;
}