BOJ 2234 : 성곽

문제링크

풀이요약

비트마스킹, BFS

풀이상세

1. 비트마스킹이 첨가된 BFS, 문제에서 1,2,4,8 가운데 벽이 있는 경우에 포함되는 방향들을 총 더한 값이 해당 a[r][c] 의 값이므로 델타값을 $\sqrt{2^n}$ 으로 으로 표현 가능하다. 즉 0,1,2,3 인 델타값의 인덱스로 표현이 가능하므로, 델타값만 서,북,동,남 순서로 맞춰주기만 하면 된다.

2. 먼저 BFS를 통해, 현재 성곽의 가장 큰 방의 크기와, 방의 총 갯수를 구한다. 이후 BFS를 통해 나오는 방의 크기를 벡터에 담아놓는다.

3. BFS 시 방문처리는 현재의 까지의 찾은 방의 갯수로 하였다. 테스트케이스로 예를 들자면 모든 BFS가 완료되는 경우 방문배열은 이러한 형태로 처리될 것이다.

   1 1 2 2 3 3 3
   1 1 1 2 3 4 3
   1 1 1 5 3 5 3
   1 5 5 5 5 5 3

4. 반복문을 통해 현재의 값과 행의 다음 값, 열의 다음 값을 보자. 만약 현재의 값과 다음의 값이 다르다면 이는 서로 벽이 있는 방이라는 것을 뜻하며, 벽을 허물 경우 두개의 방은 하나의 방이 된다. 서로 다른 방문처리 인덱스를 가진 방을 서로 합했을 때 가장 큰 값이 바로, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기이다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define f first
#define s second
using namespace std;
int N, M, a[52][52], visited[52][52];
int dr[4] = {0, -1, 0, 1}, dc[4] = {-1, 0, 1, 0};
int max_r, max_r2, r_cnt = 1;
vector<int> r_sizes;
void input() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> a[i][j];
        }
    }
}

int bfs(int r, int c, int v[][52]) {
    queue<pair<int, int>> q;
    q.push({r, c});
    v[r][c] = r_cnt;
    int ret = 1;
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        for (int b = 0; b < 4; b++) {
            if (a[curr.f][curr.s] & (1 << b)) continue;
            else {
                int nr = curr.f + dr[b];
                int nc = curr.s + dc[b];
                if (nr < 0 || nc < 0 || nr >= M || nc >= N) continue;
                if (v[nr][nc]) continue;
                v[nr][nc] = r_cnt;
                q.push({nr, nc});
                ret++;
            }
        }
    }
    return ret;
}

void solve() {
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            // 이 성의 방의 갯수 및 가장 넓은 방의 넓이 구하기.
            if(!visited[i][j]){
                int curr_room_size = bfs(i, j, visited);
                max_r = max(max_r, curr_room_size);
                r_cnt++;
                r_sizes.push_back(curr_room_size);
            }
        }
    }

    // 벽 1개를 없앨경우 얻을수 있는 가장 넓은 구간 구하기.
    for(int i=0; i<M; i++) {
        for(int j=0; j<N; j++) {
            if(i+1<M) {
                int n1 = visited[i+1][j]-1;
                int n2 = visited[i][j]-1;
                if(n1 != n2) max_r2 = max(max_r2, r_sizes[n1]+r_sizes[n2]);
            }
            if(j+1<N) {
                int n1 = visited[i][j+1]-1;
                int n2 = visited[i][j]-1;
                if(n1 != n2) max_r2 = max(max_r2, r_sizes[n1]+r_sizes[n2]);
            }
        }
    }
}

void output() {
    cout << r_cnt -1 << "\n";
    cout << max_r << "\n";
    cout << max_r2 << "\n";
}

int main() {
    input();
    solve();
    output();
}