[BOJ] 백준 2234 성곽

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

 Input 

4

7

11 6 11 6 3 10 6

7 9 6 13 5 15 5

1 10 12 7 13 7 5

13 11 10 8 10 12 13

 

 Output 

5

9

16

① BFS 탐색으로 연결되어 있는 방을 확인합니다.

    연결된 공간은 동일한 방 번호를 매기고 그 크기를 동시에 측정합니다.

② 벽이 0(0000) ~ 15(1111) 형태로 주어져 있으므로 

    벽 존재 여부는 아래와 같이 확인 가능합니다.

    

③ 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기는

    어떤 벽이든 한 곳만 뚫을 수 있으므로, 이중 for문으로 map[][]을 탐색하면서

    오른쪽과 아래쪽에 위치한 공간 확인합니다.

    같은 방번호가 아닌 경우, 두 방의 크기를 더합니다.

 

---

#include <stdio.h>
 
inline int max(int A, int B) { if (A > B) return A; return B; }
const int dx[] = { 0, -1, 0, 1 };
const int dy[] = { -1, 0, 1, 0 };
const int MAX_MN = 50;
 
struct Node {
    int x, y;
}que[MAX_MN * MAX_MN * 4];
int fr, re;
int N, M;
int map[MAX_MN][MAX_MN];
bool visited[MAX_MN][MAX_MN];
 
void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visited[i][j] = false;
        }
    }
}
 
void input() {
    scanf("%d %d", &M, &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &map[i][j]);
        }
    }
}
 
int BFS(Node start) {
    fr = re = 0;
    que[re++] = start;
    visited[start.x][start.y] = true;
 
    int roomSize = 1;
    while (fr < re) {
        Node cur = que[fr++];
        int Wall = 1;
 
        for (int i = 0; i < 4; i++) {
            if ((map[cur.x][cur.y] & Wall) != Wall) {
                int nextX = cur.x + dx[i];
                int nextY = cur.y + dy[i];
 
                if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
                    if (visited[nextX][nextY] == false) {
                        roomSize++;
                        visited[nextX][nextY] = true;
                        que[re++] = { nextX, nextY };
                    }
                }
            }
            Wall = Wall << 1;
        }
    }
    return roomSize;
}
 
void solve() {
    int roomCnt = 0;
    int maxArea = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] == false) {
                maxArea = max(maxArea, BFS({ i, j }));
                roomCnt++;
            }
        }
    }
 
    // 성에 있는 방의 개수
    printf("%d\n", roomCnt);
    // 가장 넓은 방의 넓이
    printf("%d\n", maxArea);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int Wall = 1; Wall <= 8; Wall *= 2) {
                if ((map[i][j] & Wall) == Wall) {
                    init();
                    map[i][j] = map[i][j] - Wall;
                    maxArea = max(maxArea, BFS({ i, j }));
                    map[i][j] = map[i][j] + Wall;
                }
            }
        }
    }
    // 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
    printf("%d\n", maxArea);
}
 
int main(void) {
    // freopen("input.txt", "r", stdin);
    input();
    solve();
}