[백준/C++] 2234 성곽

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

코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define MAX 51
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
typedef pair<int, int> pi;

int n, m, arr[MAX][MAX], roomCnt, maxRoomSize;
int dx[4] = { 0, -1, 0, 1 }, dy[4] = { -1, 0, 1, 0 };
bool visit[MAX][MAX];

void bfs(int x, int y) {
    int roomSize = 0;
    queue<pi> q;
    q.push({ x, y });
    visit[x][y] = true;

    while (!q.empty()) {
        int nx = q.front().first;
        int ny = q.front().second;
        q.pop();
        roomSize++;

        for (int i = 0; i < 4; i++) {
            int gx = nx + dx[i];
            int gy = ny + dy[i];

            if (gx >= 0 && gx < m && gy >= 0 && gy < n && !visit[gx][gy]) {
                if (!(arr[nx][ny] & (1 << i))) {
                    visit[gx][gy] = true;
                    q.push({ gx, gy });
                }
            }
        }
    }
    maxRoomSize = max(maxRoomSize, roomSize);
}

int main() {
    FASTIO;

    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 (!visit[i][j]) {
                bfs(i, j);
                roomCnt++;
            }
        }
    }

    cout << roomCnt << "\n" << maxRoomSize << "\n";
    maxRoomSize = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int wall = 1; wall <= 8; wall *= 2) {
                memset(visit, false, sizeof(visit));
                arr[i][j] -= wall;
                if (arr[i][j] >= 0) bfs(i, j);
                arr[i][j] += wall;
            }
        }
    }
    cout << maxRoomSize;
    return 0;
}

설명

벽 정보를 입력받은 뒤 bfs를 돌면서 1, 2번을 구합니다. 이때 서쪽 벽을 1로, 북쪽 벽을 2로, 동쪽 벽을 4, 남쪽 벽을 8료 표시하는데, 이는 곧 2의  0, 1, 2, 3 제곱입니다. 매번 bfs에서 해당 위치의 벽이 존재하는지를  비트마스킹을 이용하여 확인하고 벽이 없을 경우에만 큐에 넣어줍니다. bfs 함수의 마지막에서는 방의 최대 크기를 갱신합니다.

 

하나의 벽을 제거하는 경우에도 똑같이 bfs를 돌리면 됩니다. 다만, arr[i][j] -= wall의 결과가 음수라면 이미 해당 방향의 벽이 없는 것이므로 굳이 bfs를 진행할 필요가 없습니다. 

느낀 점

문제 자체가 힌트를 많이 주고 있다고 생각했습니다. 벽 정보를 비트마스킹을 이용해서 관리할 수 있고, 서 ➡️ 북 ➡️ 동 ➡️ 남 순으로 2배씩 값이 증가하므로 BFS 방향도 똑같이 진행합니다.  입력에서 가로, 세로 순으로 주어지는데 이 부분을 착각해서 dx, dy 배열을 바꿔서 생각했고 이 부분에서 약간 시간을 소모했습니다... 해결 후에는 BFS로 1, 2번을 구할 수 있습니다.

 

다음에는 하나의 벽을 제거해서 얻을 수 있는 가장 큰 방의 크기를 구해야 합니다. 처음에는 약간 걱정이 되었으나  n, m의 크기 제한을 보고 그냥 3중 루프로 구현했습니다. memset을 위해 cstring 헤더를 추가해야 했는데 놓쳐서 한 번 컴파일 에러가 났고, 헤더를 추가해서 제출하니 통과했습니다!