[백준/C++] 2234번 성곽

백준

---

🤔문제 이해

문제에서 요구하는 1,2,3번을 계산하되 벽에 대한 정보가 1, 2, 4, 8로 주어지는 것으로 보아 비트마스킹을 사용하면 되는 문제이다.

---

 

🔥풀이🔥

간단한 BFS를 수행하되 벽의 정보를 비트 연산으로 처리해주었다.

((1 << i) & map[y][x]) == 0)는 BFS 함수에서 왼쪽,오른쪽,위,아래로 이동하기 전에 그 방향에 벽이 있는지를 확인해주는 코드이다.

3번을 계산할 때에는 map[i][j] = map[i][j] & ~(1 << k)식을 이용해 벽을 하나씩 없앤 정보를 map에 업데이트 시켜주고 BFS를 돌린 후 map값을 초기 상태로 돌려주는 방식을 사용했다. 

 

❌트러블 슈팅

BFS를 돌기 전 시작점을 visited처리를 해주는 것을 깜빡해 오류를 찾는게 시간이 오래걸렸다.

컴파일 에러의 경우 memset 함수를 사용했는데 <cstring>헤더를 빼먹었기 때문이다.

---

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int n, m;
int map[51][51];
bool visited[51][51];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

queue<pair<int, int>> q;
int max_room;
int remove_max_room;
int cnt;
int room_size;

bool isValid(int y, int x) {
    return y < m && y >= 0 && x < n && x >= 0 && !visited[y][x];
}

void BFS() {
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        room_size++;

        for (int i = 0; i < 4; i++) {
            if (((1 << i) & map[y][x]) == 0) {
                int mv_y = y + dy[i];
                int mv_x = x + dx[i];
                if (isValid(mv_y, mv_x)) {
                    q.push({mv_y, mv_x});
                    visited[mv_y][mv_x] = true;
                }
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                visited[i][j] = true;
                cnt++;
                q.push({i, j});
                room_size = 0;
                BFS();
                if (max_room < room_size) max_room = room_size;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 4; k++) {
                memset(visited, false, sizeof(visited));
                int tmp = map[i][j];
                map[i][j] = map[i][j] & ~(1 << k);
                q.push({i, j});
                room_size = 0;
                visited[i][j] = true;
                BFS();
                remove_max_room = remove_max_room < room_size ? room_size : remove_max_room;
                map[i][j] = tmp;
            }
        }
    }
    cout << cnt << "\n" << max_room << "\n" << remove_max_room;
}