백준 2234 - 성곽(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2234

2234번: 성곽

비트연산자를 이용해 풀 때 다른 방법보다 쉽게 풀 수 있는 문제입니다.

서쪽은 1, 북쪽은 2, 동쪽은 4, 남쪽은 8의 값을 가질 때, 한 칸마다 수가 주어지는데 해당 하는 수를 통해 어디가 벽으로 막혀있는지를 알 수 있습니다.

예를 들어, 11인 경우 남쪽 + 북쪽 + 서쪽이 벽이 막혀있는 것을 구할 수 있습니다.

 

그렇다면, 벽이 어디있는지를 알아야하니 합의 조합을 통해 칸에 해당하는 값을 만들고, 이를 다른 배열에 저장해 어떻게 벽이 있는지 알아낼 수 있습니다.

하지만 비트 연산자를 이용하면 더 쉽게 구할 수 있습니다.

 

1의 값은 (1 << 0)과 같으며 8의 값은 (1 << 3)과 값이 같은데, 이를 이진수로 나타내면 0001, 0010, 0100, 1000이 됩니다.

그렇다면 11을 이진수로 나타낸 값인 1011과 1, 2, 4, 8을 비교해 같은 자리에 1이 있는지만 확인하면, 해당 하는 곳에 벽이 있다는 것을 구할 수 있습니다.

 

for(int i = 0; i < 4; i++){
    int x = map[x][y] & (1 << i);
    cout << x;
    // 이때 x의 값이 0이라면 해당 하는 곳에 벽이 없다
    // x의 값이 0이 아니라면 해당하는 곳에 벽이 있다.
}

이를 통해 알 수 있는 것은  변수 x의 값이 0이라면, 4방향 탐색 중 해당하는 방향을 갈 수 있다는 의미입니다.

따라서, 서북동남과 같은 방향인 좌상우하 의 방향으로 4방향을 저장하고 for문으로 해당하는 위치를 갈 수 있는지를 확인합니다.

 

이제 BFS 코드를 짤 수 있는데 조건을 하나만 추가하면 됩니다.

1. 해당하는 방향을 이동할 수 있어야한다.

2. 이동하려는 곳이 map 범위 안에 들어가야한다.

3. 이동하려는 곳이 이전에 방문한 곳이 아니여야 한다.
-> 3가지 조건을 순서대로 만족한다면, 해당 좌표로 이동해주면 됩니다.

 

 

이제 벽을 부술 차레입니다.

벽을 부술 때는 모든 경우를 생각해봐야 합니다.

따라서 모든 벽을 하나씩 부순 뒤, BFS를 통해 최대 방의 크기를 구한다는 것입니다.

 

벽을 부수는 것도, 비트연산을 통해 4방향 중, 해당하는 방향에 벽이 있는지를 확인한 뒤, 벽이 있으면 벽을 부순 뒤 BFS를 탐색해보고 부순 벽을 다시 붙여주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define PP pair<P, int>
#define F first
#define S second

using namespace std;

int N, M;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int map[51][51];
int check[51][51];

int bfs(int x, int y){
    int cnt = 0;
    queue<P> q;
    q.push({x, y});
    check[x][y] = 1;
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        cnt++;
        q.pop();
        for(int i = 0; i < 4; i++){
            int can_go = map[x][y] & (1 << i);
            if(!can_go){
                int xx = x + dx[i];
                int yy = y + dy[i];
                if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                    if(check[xx][yy] != 0) continue;
                    check[xx][yy] = 1;
                    q.push({xx, yy});
                }
            }
        }
    }
    return cnt;
}

void solve(){
    int room = 0, maxi = 0, combine_maxi = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(check[i][j] == 0){
                room++;
                maxi = max(maxi, bfs(i, j));
            }
        }
    }
    cout << room << "\n" << maxi << "\n";
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            for(int k = 0; k < 4; k++){
                int wall = map[i][j] & (1 << k);
                if(wall){
                    map[i][j] -= (1 << k);
                    memset(check,0, sizeof(check));
                    combine_maxi = max(combine_maxi, bfs(i, j));
                    map[i][j] += (1 << k);
                }
            }
        }
    }
    cout << combine_maxi;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> M >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요