[알고리즘] 백준 2234 성곽 // 비트마스킹, vis의 값에 의미를 부여하라, i번째 비트끄기

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

 

* 풀이1

• connted component, 구역수 세기는 잘 풀었다.
  • int dfs, 전체에대해 dfs돌리면서 cnt를 세면됨

• 방문조건에 bit가 들어간다.
  • dy,dx에 따라 동서남북을 체크하고 해당비트가 꺼져있으면 next로 이동한다.
• 문제는 벽을하나씩 부스는것이 문제다.
  • 첫풀이
    • 벽을하나씩 부스면서 (i번째 bit를 끄면서) 똑같이 dfs를 돌리고, 원복하면 될거라고 생각했다.
  • 문제점
    • 이웃한 벽도 같이 부서줘야함
    • 매번 dfs 돌기전에 vis를 초기화 해줘야함
    • 현재는 벽제거후 그곳에서만 dfs호출, 벽을제거한후 모든 지점에서 dfs를 호출해야 완탐이됨

//n^2 C 1 * 4(동서남북) 벽제거
     memset(vis,0,sizeof(vis));
     for(int i=0;i<m;++i) {
         for(int j=0;j<n;++j) {
             // if(vis[i][j]) continue;
             for(int k=0;k<4;++k) {
                 int mask = ~(1<<k); //k번째 비트 끄기
                 int origin = arr[i][j];
                 arr[i][j]&= mask;
                 dfs3(i,j);
                 arr[i][j]=origin;
             }
         }
     }
     //벽을 하나씩 제거해보면서 최대 크기 계산

 

* 개념정리

• i번째 비트끄는법
  • mask = (1<<i)
  • ~mask
  • 원본 = 원본 & mask

• 이웃 벽 구하기
  • (k+2)%4 공식이 나온 이유를 설명드리겠습니다:
    1. 방향 인덱스(k)는 다음과 같이 정의되어 있습니다:
       • 0: 남쪽 (bit: 8)
       • 1: 동쪽 (bit: 4)
       • 2: 북쪽 (bit: 2)
       • 3: 서쪽 (bit: 1)
    2. 각 방향의 반대 방향은:
       • 남쪽(0)의 반대는 북쪽(2)
       • 동쪽(1)의 반대는 서쪽(3)
       • 북쪽(2)의 반대는 남쪽(0)
       • 서쪽(3)의 반대는 동쪽(1)
    3. 규칙을 보면:
       • 현재 인덱스에 2를 더하고
       • 4로 나눈 나머지를 구하면
       • 반대 방향의 인덱스가 나옵니다.
    따라서 (k+2)%4는 현재 방향의 반대 방향 인덱스를 구하는 간단한 수식이 됩니다.
     
    이 공식을 사용하면 어떤 방향이든 그 반대 방향을 쉽게 계산할 수 있습니다.

 

* 코드1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m,ret1,ret2, ret3; //방의갯수, 가장 넓은방의 넓이
int arr[54][54], vis[54][54];
int dy[]={1,0,-1,0}; //남, 동, 북, 서
int dx[]={0,1,0,-1};
int bit[]={8,4,2,1}; // 각 방향에 해당하는 비트값 추가

int dfs(int y, int x) {
    vis[y][x]=1;
    int cnt=1;

    for(int i=0;i<4;++i) {
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(ny<0 || nx<0 || ny>=m || nx>=n) continue;
        if(vis[ny][nx]) continue;
        if(i==0 && !(arr[y][x]&8)) {
            cnt+=dfs(ny,nx);
        }
        if(i==1 && !(arr[y][x]&4)) {
            cnt+=dfs(ny,nx);
        }
        if(i==2 && !(arr[y][x]&2)) {
            cnt+=dfs(ny,nx);
        }
        if(i==3 && !(arr[y][x]&1)) {
            cnt+=dfs(ny,nx);
        }
    }
    ret2=max(ret2,cnt);
    return cnt;
}

int dfs3(int y, int x) {
    vis[y][x]=1;
    int cnt=1;

    for(int i=0;i<4;++i) {
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(ny<0 || nx<0 || ny>=m || nx>=n) continue;
        if(vis[ny][nx]) continue;
        if(i==0 && !(arr[y][x]&8)) {
            cnt+=dfs3(ny,nx);
        }
        if(i==1 && !(arr[y][x]&4)) {
            cnt+=dfs3(ny,nx);
        }
        if(i==2 && !(arr[y][x]&2)) {
            cnt+=dfs3(ny,nx);
        }
        if(i==3 && !(arr[y][x]&1)) {
            cnt+=dfs3(ny,nx);
        }
    }
    ret3=max(ret3,cnt);
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    
    for(int i=0;i<m;++i) {
        for(int j=0;j<n;++j) {
            cin>>arr[i][j];
        }
    }

    for(int i=0;i<m;++i) {
        for(int j=0;j<n;++j) {
            if(vis[i][j]) continue;
            dfs(i,j);
            ret1++;
        }
    }

    //n^2 C 1 * 4(동서남북) 벽제거
     // memset(vis,0,sizeof(vis));
     // for(int i=0;i<m;++i) {
     //     for(int j=0;j<n;++j) {
     //         // if(vis[i][j]) continue;
     //         for(int k=0;k<4;++k) {
     //             int mask = ~(1<<k); //k번째 비트 끄기
     //             int origin = arr[i][j];
     //             arr[i][j]&= mask;
     //             dfs3(i,j);
     //             arr[i][j]=origin;
     //         }
     //     }
     // }
    // 벽을 하나씩 제거하면서 최대 크기 찾기
    for(int i=0;i<m;++i) {
        for(int j=0;j<n;++j) {
            for(int k=0;k<4;++k) {
                // 현재 위치에 벽이 있고, 다음 위치가 유효한 경우만 시도
                if((arr[i][j] & bit[k])) {
                    int ny = i + dy[k];
                    int nx = j + dx[k];
                    if(ny<0 || nx<0 || ny>=m || nx>=n) continue;
                    
                    // 현재 위치와 다음 위치의 벽을 제거
                    int origin = arr[i][j];
                    int next_origin = arr[ny][nx];
                    arr[i][j] &= ~bit[k];
                    arr[ny][nx] &= ~bit[(k+2)%4];
                    
                    // 전체 맵에서 최대 크기 찾기
                    memset(vis, 0, sizeof(vis));
                    int temp = 0;
                    for(int y=0;y<m;++y) {
                        for(int x=0;x<n;++x) {
                            if(!vis[y][x]) {
                                temp = max(temp, dfs3(y,x));
                            }
                        }
                    }
                    ret3 = max(ret3, temp);
                    
                    // 벽 복구
                    arr[i][j] = origin;
                    arr[ny][nx] = next_origin;
                }
            }
        }
    }
    cout<<ret1<<"\n"<<ret2<<"\n"<<ret3;
    
    return 0;
}

 

* 큰돌풀이

vis의 값에 의미를 부여하라

• visited에 각 칸이 어떤 방에 속하는지 저장 (방 번호로 표시) => 합칠때 다른 방인지 확인후 합치기
• 우측, 아래 방향으로만 탐색

• 비트 확인 일반화

• 외곽은 항상벽 -> ny,nx 범위검사 불필요
• cnt는 방의 id 역할

#include <bits/stdc++.h>
using namespace std;   

// 상하좌우 이동을 위한 방향 배열 (서, 북, 동, 남 순서)
const int dy[] = {0, -1, 0, 1};  
const int dx[] = {-1, 0, 1, 0}; 

// visited: 각 칸이 어떤 방에 속하는지 저장 (방 번호로 표시)
// a: 입력받은 맵 정보 저장
// cnt: 방의 총 개수
// compSize: 각 방의 크기를 저장하는 배열 (인덱스는 방 번호)
// n, m: 맵의 가로, 세로 크기
// mx: 가장 큰 방의 크기
// big: 벽을 하나 제거하여 얻을 수 있는 가장 큰 방의 크기
int visited[51][51], a[51][51], cnt, compSize[2504], n, m, mx, big; 

// DFS로 연결된 방의 크기를 계산하는 함수
// y, x: 현재 위치
// cnt: 현재 탐색중인 방의 번호
int dfs(int y, int x, int cnt){
   // 이미 방문한 칸이면 0 리턴
   if(visited[y][x]) return 0; 
   
   // 현재 칸에 방 번호를 기록
   visited[y][x] = cnt; 
   
   // 현재 칸을 포함하여 1부터 시작
   int ret = 1; 
   
   // 4방향 탐색
   for(int i = 0; i < 4; i++){
       // 현재 방향에 벽이 없으면 (비트 연산으로 확인)
       if(!(a[y][x] & (1 << i))){
           // 다음 칸의 좌표 계산
           int ny = y + dy[i]; 
           int nx = x + dx[i]; 
           // 다음 칸을 탐색하여 크기를 누적
           ret += dfs(ny, nx, cnt); 
       } 
   } 
   return ret; 
}

int main(){
   // 입력 받기
   cin >> n >> m;
   for(int i = 0; i < m; i++){
       for(int j = 0; j < n; j++){
           cin >> a[i][j]; 
       }
   }

   // 전체 맵을 탐색하면서 방 찾기
   for(int i = 0; i < m; i++){
       for(int j = 0; j < n; j++){
           // 아직 방문하지 않은 칸이면
           if(!visited[i][j]){
               cnt++;  // 새로운 방 발견
               // 현재 방의 크기를 계산하여 저장
               compSize[cnt] = dfs(i, j, cnt);  
               // 가장 큰 방의 크기 갱신
               mx = max(mx, compSize[cnt]);
           } 
       }
   }

   // 벽을 하나 제거할 때 얻을 수 있는 가장 큰 방 크기 계산
   for(int i = 0; i < m; i++){
       for(int j = 0; j < n; j++){
           // 아래쪽 방과 합치기
           if(i + 1 < m){  // 맵을 벗어나지 않는지 확인
               int a = visited[i + 1][j];  // 아래쪽 방의 번호
               int b = visited[i][j];      // 현재 방의 번호
               if(a != b){  // 서로 다른 방이면
                   // 두 방의 크기를 합쳐서 최대값 갱신
                   big = max(big, compSize[a] + compSize[b]); 
               }
           }
           // 오른쪽 방과 합치기 (위와 동일한 로직)
           if(j + 1 < n){
               int a = visited[i][j + 1]; 
               int b = visited[i][j]; 
               if(a != b){ 
                   big = max(big, compSize[a] + compSize[b]); 
               }
           } 
       } 
   } 

   // 결과 출력
   // 1. 방의 개수
   // 2. 가장 큰 방의 크기
   // 3. 벽을 하나 제거하여 얻을 수 있는 가장 큰 방의 크기
   cout << cnt << "\n" << mx << "\n" << big <<'\n'; 
   return 0;
}