[2234] 성곽

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

2234번: 성곽

<문제>

모든 방문하지 않은 구역에 대해서 번호 라벨링 + 구역 넓이 저장을 해두었다면

"하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기"를 구할 수 있다.

위를 구하는 과정에서 자연스럽게 방의 개수와 가장 큰 방의 크기를 구할수 있으므로

bfs를 통해 해당 구역의 번호와 넓이만 저장하면 된다.

비트마스킹을 통해 벽의 여부를 판별해야 하고, 서북동남 순서로 방향데이터를 만들어야 한다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, numOfRoom, maxArea, maxArea2, a[55][55], area[55][55], label[55][55],
    dy[4] = {0, -1, 0, 1}, dx[4] = {-1, 0, 1, 0};
 
bool visited[55][55];
void f(int sy, int sx) {
    visited[sy][sx] = true;
    queue<pair<int, int>> q;
    q.push({sy, sx});
    int cnt = 1;
    vector<pair<int, int>> v;
    v.push_back({sy, sx});
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            if (a[cur.first][cur.second] & (1 << i)) continue;
            int y = cur.first + dy[i];
            int x = cur.second + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (visited[y][x] == true) continue;
            visited[y][x] = true;
            q.push({y, x});
            cnt++;
            v.push_back({y, x});
        }
    }
    maxArea = max(cnt, maxArea);
    for (auto& x : v) {
        area[x.first][x.second] = cnt;
        label[x.first][x.second] = numOfRoom;
    }
}
int main(void) {
    cin >> m >> n;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) cin >> a[i][j];
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            if (visited[i][j] == false) {
                numOfRoom++;
                f(i, j);
            }
        }
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            for (int dir = 0; dir < 4; dir++) {
                int y = i + dy[dir];
                int x = j + dx[dir];
                if (y < 0 || x < 0 || y >= n || x >= m) continue;
                if (label[i][j] == label[y][x]) continue;
                int score = area[i][j] + area[y][x];
                maxArea2 = max(score, maxArea2);
            }
    cout << numOfRoom << '\n' << maxArea << '\n' << maxArea2;
    return 0;
}