[백준/Baekjoon] 2234 성곽 C++ :: BFS & Bit masking

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

2234번: 성곽

---

1. Logic

좌상우하 순서대로 1, 2, 4, 8이라는 값을 가지고 있기 때문에 이는 비트마스킹으로 쉽게 표현할 수 있다.

 

13을 예시로 들어보면 13을 2진수로 표현하게 되면 1101이다. 즉 13인 방에서 갈수있는 방향을 왼쪽 오른쪽 아래 총 3가지 방향만 갈 수 있다. BFS를 돌 때 dir방향인 dy[4] dx[4]배열을 만들어 놓는데 이와 같은 방향일 때 내가 있는 공간에서 막혀있는 방향이면 BFS로직에서 continue해주면 된다.

 

1번과 2번은 이 방법대로 구할 수 있는데 3번 문제를 구하는 방법이 되게 신박했다.

 

BFS를 도는 로직은 똑같지만 모든 칸에 대해서 완전탐색을 돌고 BFS를 들어가기 전에 shift 연산으로 1,2,4,8 즉 벽을 하나씩 허물어 놓은 상태로 BFS를 들어가서 방의 최대 갯수를 도출한다. 그리고 BFS로직이 끝나면 다시 벽을 만들어준다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n, m;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int graph[51][51];
bool vis[51][51];

int roomCnt = 0;
int maxRoom = 0;
int breakMaxRoomCnt = 0;

int BFS(int yy, int xx) {
    queue<pair<int, int>> q;
    
    int cnt = 0;
    q.push({yy, xx});
    vis[yy][xx] = true;
    
    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        cnt++;
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            if(vis[ny][nx]) continue;
            
            if((graph[y][x] & (1 << i))) continue;
            q.push({ny, nx});
            vis[ny][nx] = true;
        }
    }
    
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> m >> n;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> graph[i][j];
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(vis[i][j]) continue;
            maxRoom = max(maxRoom, BFS(i, j));
            roomCnt++;
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            for(int k = 1; k <= 8; k <<= 1) {
                if(graph[i][j] & k) {
                    memset(vis, false, sizeof(vis));
                    graph[i][j] -= k;
                    breakMaxRoomCnt = max(breakMaxRoomCnt, BFS(i, j));
                    graph[i][j] += k;
                }
            }
        }
    }
    
    cout << roomCnt << '\n';
    cout << maxRoom << '\n';
    cout << breakMaxRoomCnt << '\n';
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐