[백준 2234] 성곽 (C++)

2234번: 성곽

비트마스킹, BFS

---

 

[백준 16946] 벽 부수고 이동하기 4 (C++)

위 문제와 아주 비슷한 방법을 적용해서 풀었다.

 

차이점은 N과 M의 크기가 현재 문제에서는 50, 50이 최대라서 O(N^2 * M^2)이 가능하다는 점이다.

이때문에 풀이가 비슷함에도 불구하고 난이도 차이가 2단계나 난 것 같다.

 

Map의 각 칸마다 0~15까지의 주어진 수를 저장해놓고 연속된 칸을 찾기위해서 bfs를 수행했다.

문제에서 대놓고 비트마스킹을 사용하라고 해서 편하게 적용할 수 있었다.

dir[]배열의 순서가 서, 북, 동, 남 이므로 dr[], dc[]배열도 서, 북, 동, 남 순으로 배치해 주었다.

다음 칸을 아직 방문하지 않았고 해당 방향으로 벽이 뚫려 있다면 탐색할 수 있게 하고, 현재 bfs의 setcount를 각 칸에 맞는 setMap[][]의 값으로 설정해 주었다. 

위 과정에서 1, 2번 답을 구할 수 있다.

 

그리고 3번 답을 구하기 위해서 모든 칸들을 순회한다.

현재 칸에서 4방향으로 둘러보고 인접 칸이 현재 칸과 같은 집합이 아니라면 인접 칸의 크기를 더해준다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
int Map[51][51];
int setMap[51][51];
int setnum[2505];
int setcount = 1;
int dr[4] = {0, -1, 0, 1}, dc[4] = {-1, 0, 1, 0};
int dir[4] = {1, 1 << 1, 1 << 2, 1 << 3}; // 서 북 동 남
 
void input(){
    cin >> M >> N;
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            cin >> Map[r][c];
        }
    }
}
 
int bfs12(int r, int c){
    int cnt = 0;
    queue<pii > que;
    que.push({r, c});
    
    setMap[r][c] = setcount;
    
    while(!que.empty()){
        pii now = que.front();
        que.pop();
        cnt++;
        
        for(int k = 0; k < 4; k++){
            int nr = now.first + dr[k];
            int nc = now.second + dc[k];
            // 뚫려 있는 경우
            if(!(dir[k] & Map[now.first][now.second]) && !setMap[nr][nc]){
                setMap[nr][nc] = setcount;
                que.push({nr, nc});
            }
        }
    }
    setnum[setcount] = cnt;
    setcount++;
    return cnt;
}
 
 
int find3(int r, int c){
    int ret = setnum[setMap[r][c]];
    for(int k = 0; k < 4; k++){
        int nr = r + dr[k];
        int nc = c + dc[k];
        if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
        if(setMap[nr][nc] != setMap[r][c]){
            ret = max(ret, setnum[setMap[r][c]] + setnum[setMap[nr][nc]]);
        }
    }
    
    return ret;
}
 
void solve(){
    int number_of_rooms_in_this_castle = 0, largest_room_area = 0;
    int largest_room_size_obtained_by_removing_one_wall = 0;
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(setMap[r][c]) continue;
            largest_room_area = max(largest_room_area, bfs12(r, c));
            number_of_rooms_in_this_castle++;
        }
    }
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            largest_room_size_obtained_by_removing_one_wall = \
            max(largest_room_size_obtained_by_removing_one_wall, find3(r, c));
        }
    }
    
    cout << number_of_rooms_in_this_castle << "\n";
    cout << largest_room_area << "\n";
    cout << largest_room_size_obtained_by_removing_one_wall << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}