문제

문제 링크

해설

• DFS + 비트마스킹 + 구현 문제입니다.
  • 요구조건 1, 2번은 전형적인 connected component 찾기 문제입니다.
  • (0, 0)부터 (N - 1, M - 1)까지 visited[][] 배열을 잘 사용하면서 DFS를 사용해 연결된 요소가 몇 개인지, 각각의 넓이는 몇인지 구하면 됩니다.
  • 요구조건 3번이 조금 까다로운데, 비트마스킹 + 구현 개념이 들어가기 때문입니다.
• 이러한 문제는 dy, dx를 (y, x)에 더해서 다음 좌표가 범위를 넘어갔는지 검사한 뒤 이동하는 것이 전형적이었습니다.
  • 이 문제는 '벽'이라는 개념을1, 2, 4, 8 로 (마치 대놓고 비트마스킹을 쓰라는 듯) 표현하고 있기 때문에
  • 인접한 칸으로 이동하기 위해서는 유효한 범위에 있는지 + 벽이 뚫려 있는지를 검사해야 합니다.
• 벽이 뚫려있는지 검사한다는 게 어떤 뜻일까요?
  • (y, x)에서 오른쪽으로 이동하고 싶다면,
    • (y, x+1)은 왼쪽벽이 뚫려 있어야 하고,
    • (y, x)는 오른쪽벽이 뚫려 있어야 겠죠?
  • 그러므로 ((y, x) & 4) && ((y, x+1) & 1) == 0 이어야 합니다.
  • 이런 식으로 ⓐ 유효한 범위인지 ⓑ 방문했는지 ⓒ 벽을 통과할 수 있는지를 검사하면서 DFS를 수행하면 됩니다.

• 마지막으로, 벽 1개를 제거한다는 것은 어떤 의미일까요?
• 위 그림을 보면, (0, 0)부터 (N-2, M-2)까지는 각 칸마다 아랫쪽벽, 오른쪽벽을 제거할 수 있습니다. (빨간선으로 표시)
• 가장 오른쪽칸 (y, M-1)은 아랫쪽벽만 제거할 수 있습니다. (노란색선으로 표시)
• 가장 아랫쪽칸 (N-1, x)는 오른쪽벽만 제거할 수 있습니다. (초록색선으로 표시)
• 각 벽을 제거한 뒤 DFS를 수행하고, 넓이를 계산한 뒤, 다시 복원하는 과정을 반복하면 됩니다. 시간 내에 풀이할 수 있습니다.

코드

#include <iostream>
#include <array>
#include <functional>
using namespace std;

// 이동 순서: 왼쪽, 위쪽, 오른쪽, 아래쪽
constexpr int d[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
constexpr int LEFT = 0, UP = 1, RIGHT = 2, DOWN = 3;

int N, M;
array<array<int, 50>, 50> castle;
array<array<bool, 50>, 50> visited;

// 이동 순서에 맞춰서: [0]:왼쪽, [1]: 위쪽, [2]: 오른쪽, [3]: 아래쪽 이동
function<bool(int, int)> is_valid[4] {
    {[](int y, int x){ return ((x < M - 1)  && !(castle[y][x + 1] & 1) && !(castle[y][x] & 4)); }},
    {[](int y, int x){ return ((y < N - 1)  && !(castle[y + 1][x] & 2) && !(castle[y][x] & 8)); }},
    {[](int y, int x){ return ((x > 0)      && !(castle[y][x - 1] & 4) && !(castle[y][x] & 1)); }},
    {[](int y, int x){ return ((y > 0)      && !(castle[y - 1][x] & 8) && !(castle[y][x] & 2)); }}
};

inline void destroy_wall(int& target, int direction) {
    target &= ~(1 << direction);
}

inline void restore_wall(int& target, int direction) {
    target |= (1 << direction);
}

inline bool check_wall(int target, int direction) {
    return target & (1 << direction);
}

void DFS(int y, int x, int& area) {
    area++;
    visited[y][x] = true;
    for (int i = 0; i < 4; ++i) {
        int ny = y + d[i][0], nx = x + d[i][1];
        if (ny < 0 || nx < 0 || ny >= N || nx >= M || visited[ny][nx] || !is_valid[i](ny, nx)) continue;
        DFS(ny, nx, area);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> M >> N;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < M; ++x)
            cin >> castle[y][x];
    
    // 1. 방의 갯수 + 2. 가장 넓은 방의 넓이
    int room_cnt = 0;
    int room_max_area = 0;
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < M; ++x) {
            if (visited[y][x]) continue;
            int room_area = 0;
            DFS(y, x, room_area);
            room_max_area = max(room_max_area, room_area);
            room_cnt++;
        }
    }
    // 3. 하나의 벽을 제거해 얻을 수 있는 가장 넓은 방의 크기
    int modified_room_max_area = 0;
    for (int y = 0; y < N - 1; ++y) {
        for (int x = 0; x < M - 1; ++x) {
            // 아래쪽 벽이 없다면 생략합니다.
            if (!check_wall(castle[y][x], DOWN)) continue;
            visited.fill(array<bool, 50>{});        // clear (memset)
            
            destroy_wall(castle[y][x], DOWN);       // 아래쪽 벽을 제거합니다.
            destroy_wall(castle[y + 1][x], UP);     // 아랫칸의 위쪽 벽을 제거합니다.
            int room_area = 0;
            DFS(y, x, room_area);
            modified_room_max_area = max(modified_room_max_area, room_area);
            restore_wall(castle[y + 1][x], UP);     // 아랫칸의 위쪽 벽을 복원합니다.
            restore_wall(castle[y][x], DOWN);       // 아래쪽 벽을 복원합니다.
            
            // 오른쪽 벽이 없다면 생략합니다.
            if (!check_wall(castle[y][x], RIGHT)) continue;
            visited.fill(array<bool, 50>{});        // clear (memset)

            destroy_wall(castle[y][x], RIGHT);      // 오른쪽 벽을 제거합니다.
            destroy_wall(castle[y][x + 1], LEFT);   // 오른쪽 칸의 왼쪽 벽을 제거합니다.
            room_area = 0;
            DFS(y, x, room_area);
            modified_room_max_area = max(modified_room_max_area, room_area);
            restore_wall(castle[y][x + 1], LEFT);   // 오른쪽 칸의 왼쪽 벽을 복원합니다.
            restore_wall(castle[y][x], RIGHT);      // 오른쪽 벽을 복원합니다.
        }
    }
    // 마지막 행은 아래쪽을 검사할 필요가 없습니다.
    for (int y = N - 1, x = 0; x < M - 1; ++x) {
        if (!check_wall(castle[y][x], RIGHT)) continue;
        visited.fill(array<bool, 50>{});

        destroy_wall(castle[y][x], RIGHT);
        destroy_wall(castle[y][x + 1], LEFT);
        int room_area = 0;
        DFS(y, x, room_area);
        modified_room_max_area = max(modified_room_max_area, room_area);
        restore_wall(castle[y][x + 1], LEFT);
        restore_wall(castle[y][x], RIGHT);
    }
    // 마지막 열은 오른쪽을 검사할 필요가 없습니다.
    for (int x = M - 1, y = 0; y < N - 1; ++y) {
        if (!check_wall(castle[y][x], DOWN)) continue;
        visited.fill(array<bool, 50>{});

        destroy_wall(castle[y][x], DOWN);
        destroy_wall(castle[y + 1][x], UP);
        int room_area = 0;
        DFS(y, x, room_area);
        modified_room_max_area = max(modified_room_max_area, room_area);
        restore_wall(castle[y + 1][x], UP);
        restore_wall(castle[y][x], DOWN);
    }
    cout << room_cnt << '\n';
    cout << room_max_area << '\n';
    cout << modified_room_max_area << '\n';
}

소스코드 링크

결과