[BOJ] 2234. 성곽

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

2234번: 성곽

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

를 구하는 문제이다. 이 문제는 bfs와 비트 마스크를 사용해서 풀었다.

 

 

먼저 1번과 2번문제에 대한 답을 먼저 구하였다.

방문하지 않은 모든 칸에 bfs를 사용하여 방문하고 bfs가 시작될 때마다(새로운 방이므로) 방 개수를 늘려준다.

그리고 bfs탐색을 할때마다 방문하는 칸의 개수를 세줘서 방의 넓이를 구하여 방의 넓이 중 최댓값을 구할 수 있다.

 

이 문제에서 bfs를 할 때 중요한 부분은 벽인지 아닌지 알아내야 한다.

 

 

벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

라고 문제 입력에서 주어지는데 이 부분이 힌트인 것 같다. 그림으로 나타내면 아래와 같다.

 

 

 

 

문제에서 주어진 예시 그림(맨 위 그림)의 왼쪽 끝칸(0,0)을 예시로 들어보면 아래 그림과 같다. 서쪽, 북쪽, 남쪽에 벽이 있기 때문에

1+2+8 = 11로 11이 문제 입력에서 주어진다. 11은 다시 이진수로 1011로 나타낼 수 있으므로 이를 이용해서 비트 마스크로 검사를 한다.

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

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

먼저 방향 배열을 서, 북, 동, 남 순서로 해놓아야 한다. 그래야 1 << 0을 했을 때의 값이 1이므로 서쪽을 표현할 수 있고 1<<1 은 2로 북쪽을 표현할 수 있다.

그리고 검사할 칸과 & (1<<k)를 해서 해당 위치에 1을 가지고 있는지 검사한다. (k는 0부터 3으로 네 방향의 index)

1을 가지고 있는 경우(위의 연산 결과가 0이 아닌 경우)에는 벽이므로 해당 방향으로는 이동하지 않는다.

 

 

그리고 나중에 3번 문제를 해결하기 위해서플러드 필 알고리즘(연결 요소에 번호를 매김)을 사용한다. bfs를 할 때 현재 연결된 칸들에 방 번호를 매겨주고 각 방의 넓이 또한 cnt 배열에 저장해놓는다.

 

 

3번 문제를 해결하기 위해서는 다음과 같은 생각을 했다.

인접해있는 방과 현재 방의 넓이를 합쳤을 때의 최댓값이 하나의 벽을 제거했을 때의 결과와 마찬가지다.

아래 그림을 봤을 때 1번 방은 2번 방과 3번 방과 인접해있는데 3번 방과 인접해있는 벽 중 하나를 제거했을 때 최댓값을 얻을 수 있다.

 

 

코드로 구현하자면 다시 새로운 bfs를 이용한다. 이때 bfs에서는 아까 플러드 필 알고리즘을 사용하여 방 번호를 매긴 배열을 이용한다.

이동했을 때 같은 방인 경우에는 계속 큐에 넣고 방문 체크를 해주며 탐색을 이어가고 같은 방이 아닌 경우에는 현재 방의 칸수와 옆의 방의 칸수를 합친 값(위에서 저장한 cnt배열을 이용)을 저장하고 이 합쳐진 값들 중 최댓값이 정답이 된다.

 

1번 방에 대해 인접한 방에 대해서 모두 탐색을 해봤다면 다음 2번 방을 검사할 때는 다시 1번 방과 비교할 필요는 없다.

그러므로 bfs로 방문한 칸은 모두 다 체크해주면 된다.

 

 

역시 코드를 보는 게 가장 이해하기 쉬울 것 같다ㅎㅎ

순서는 main -> solve -> bfs 다음에 removeWall -> bfs2로 진행된다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int m, n;
int map[50][50];
int visit[50][50];
bool check[50][50];
int cnt[2500];
 
 
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
 
int bfs2(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    int sum = 0;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (check[nx][ny]) continue;
 
 
            //같은 방이면 큐에 넣고
            if (visit[nx][ny] == visit[x][y]) {
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
            }
            else { //다른 방이면 그 방과 합쳐졌을 때의 넓이를 저장
                int tmp = cnt[visit[x][y]] + cnt[visit[nx][ny]];
                if (sum < tmp) sum = tmp;
            }
 
        }
    }
 
    return sum;
 
}
 
void removeWall() {
    queue<pair<int, int>> q;
 
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (check[i][j]) continue;
            int tmp = bfs2(i, j);
            if (sum < tmp) sum = tmp;
        }
    }
    
    cout << sum << '\n';
}
 
int bfs(int x, int y, int num) {
    int cnt = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    visit[x][y] = num;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            //해당 방향이 벽인 경우
            if (map[x][y] & (1 << k)) continue;
 
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visit[nx][ny]) continue;
 
            q.push(make_pair(nx, ny));
 
            //방 번호를 기록
            visit[nx][ny] = num;
            cnt++;
        }
 
    }
 
 
    //연결된 칸의 개수를 리턴(방의 넓이)
    return cnt;
}
 
void solve() {
 
    int maxcnt = 0;
    int roomcnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visit[i][j]) continue;
 
            //bfs출발할 때마다 방의 개수 늘어난다
            int tmp = bfs(i, j, ++roomcnt);
 
            //방 별로 넓이를 저장해놓는다.
            cnt[roomcnt] = tmp;
 
            //가장 넓은 방의 넓이
            if (maxcnt < tmp) maxcnt = tmp;
        }
    }
 
    //1번 답 출력
    cout << roomcnt << "\n";
 
    //2번 답 출력
    cout << maxcnt << "\n";
 
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> m >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    //1번과 2번 답을 구한다
    solve();
 
    //3번 답을 구한다
    removeWall();
 
    return 0;
}