[BOJ 2234] 성곽

#문제

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

#풀이

해당 문제는 BFS를 사용하면 손쉽게 풀 수 있습니다.

우선 저는 맵에서 칸마다 벽이 있고 없고의 유무를 주었습니다.

10진수로 주어진 값을 2진수로 바꾸어 어디 방향에 벽이 있는지 알아야합니다.

예로 11이 들어왔을때, 11은 1011로 나타낼 수 있고 앞자리부터 순서대로 남, 동, 북, 서에 벽이 있는지 없는지 유무를 나타냅니다.

따라서 11은 남, 북, 서에 벽이 있으며 동으로 움직일 수 있다는 뜻이 됩니다.

이때, 방향을 잘 기억해 두는 것이 좋습니다.

해당 방향의 순서들이 한번 더 사용할 곳이 있습니다! 이는 좀있다가 알아보도록 하죠!

또한 6(0110)과 같이 4자리가 꽉 채워지지 않는 수들은 앞에 '0'을 붙혀 4자리를 꽉 채우게끔 만들어주었습니다.

이렇게 맵을 다 채웠다면, 1번 2번 3번 문제에 답을 해주어야 합니다.

DFS로 풀어도 되지만 저는 BFS를 사용하여 풀었습니다!

해당 소 문제들은 단지번호 붙히기와 거의 유사하게 풀 수 있습니다.

저는 단지번호 붙히기 문제를 DFS로 풀었었네요. BFS로 접근하기 잘한것 같습니다 :)

BFS는 시작점을 큐에 넣어두고 다음 위치로 갈 수 있는 곳인지 확인하고 갈 수 있다면 큐에 다음 위치를 넣는 형식으로 진행됩니다.

이때, 중요한것이 아까 방향! 남, 동, 북, 서 순으로 갈 위치와 벽을 확인한다면 쉽게 확인이 가능하겠죠? 

다른 때는 순서를 보통 북,남,서,동 순으로 놓지만, 이번에는 다르게 남, 동, 북, 서 순으로 두었습니다.

방향 순서대로 벽을 확인하고 벽이 없다면 통과! 

이후 과정은 다른 문제들과 거의 흡사합니다.

방의 개수도 알아야하기 때문에 큐에 들어갈 때마다 개수를 증가 시켜주어 마지막에 리턴 시켜주었습니다..

모든 방의 시작점들이 다르므로 모든 위치에서 확인을 해주고 시작점일 때마다 또 개수를 증가시켜 몇개의 방이 있는지 확인합니다.

이로써 소문제 1번이 해결이 됬네요!! :)

소문제 2번은 아까 리턴했던 개수들 중에서 가장 큰 값을 뽑아내면 됩니다.

이제 남은 것은 소문제 3번입니다.

벽 한칸을 없앴을때 최대 방의 크기를 구하는 문제로 소문제 2번과 거의 흡사합니다.

하지만, 어떤 벽을 없앴을때 커지는지 모르므로 모든 벽을 한 번씩 없애 확인하였습니다.

벽을 허물 경우의 수는 맵의 크기가 50*50 이고 벽이 한칸당 4개가 있으므로 최대 50*50*4*1(행 * 열 * 방향 * 없애는 개수)번입니다.

여기서 중요한 포인트가 나오는데, 아까 위 두 소문제 처럼 모든 방의 시작점에서 확인을 하지 않아도 된다는 것입니다.

왜?! 한개의 벽만 허물어 해당 벽을 공유한 두개의 방만 새롭게 한방이 되며 나머지 방들은 기존에 구했던 값과 같아지기 때문입니다.

잡 Tip! 맵의 외각에 있는 벽들은 없어져도 그곳으로 나갈 수 없으니 미리 빼준다면 시간이 조금이라도 절약될 것입니다.

이로써 소문제 3도 끝! 코드를 보며 이해를 해봅시다!

#코드

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
 
struct Wall {
public:
    // 0->남, 1->동, 2->북, 3->서
    bool dir[4];
    Wall(){
        memset(dir, false, sizeof(dir));
    }
    Wall(string binary){
        memset(dir, false, sizeof(dir));
        for(int i = 0; i < 4; i++){
            if(binary[i] == '1')
                dir[i] = true;
        }
    }
};
 
int n,m;
int map[50][50];
Wall wall[50][50];
bool visit[50][50];
 
int dr[4] = {1,0,-1,0};
int dc[4] = {0,1,0,-1};
 
int bfs(int r, int c){
    queue<pair<int, int>> q;
    q.push({r,c});
    visit[r][c] = true;
    int cnt = 1;
    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            if(wall[r][c].dir[i]) continue;
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if(visit[nr][nc]) continue;
            q.push({nr,nc});
            visit[nr][nc] = true;
            cnt++;
        }
    }
    return cnt;
}
 
void answerQuestion(){
    int roomNum = 0, roomSize = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(!visit[i][j]){
                //소문제 1
                roomNum++;
                int size = bfs(i,j);
                //소문제 2
                if(roomSize < size)
                    roomSize = size;
            }
        }
    }
    cout << roomNum << endl;
    cout << roomSize << endl;
    //소문제 3
    int maxRoomSize = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < 4; k++){
                //외각 벽은 허물지 않는다
                if(i == 0 && k == 2) continue;
                if(i == m-1 && k == 0) continue;
                if(j == 0 && k == 3) continue;
                if(j == n-1 && k == 1) continue;
                //만약 허물 벽이 없다면 무시
                if(!wall[i][j].dir[k]) continue;
                
                memset(visit, false, sizeof(visit));
                wall[i][j].dir[k] = false;
                int size = bfs(i,j);
                if(size > maxRoomSize) maxRoomSize = size;
                wall[i][j].dir[k] = true;
            }
        }
    }
    cout << maxRoomSize << endl;
}
 
string changeBinary(int num){
    string binary = "";
    while(num > 0){
        if(num % 2 == 1){
            binary = '1'+ binary;
        }else{
            binary = '0' + binary;
        }
        num /= 2;
    }
    while(binary.size() < 4){
        binary =  '0' + binary;
    }
    return binary;
}
 
int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            int num;
            cin >> num;
            string binary = changeBinary(num);
            Wall w(binary);
            wall[i][j] = w;
        }
    }
    answerQuestion();
    return 0;
}