백준 2234번 성곽 - C++ 풀이

---

 

1. DFS/BFS를 사용해서 방의 개수를 센다.
2. DFS/BFS를 사용해서 각 방의 넓이를 구한다.
3. 2에서 구한 값을 사용하여 모든 벽에 대해 해당 벽을 제거했을 때 얻을 수 있는 방의 크기를 구한다.

 

1. DFS/BFS를 사용해서 방의 개수를 센다.

 방의 개수는 연결 요소의 개수와 같다. DFS나 BFS를 사용하여 연결 요소의 개수를 세준다.

 

2. DFS/BFS를 사용해서 각 방의 넓이를 구한다.

 각 방의 넓이는 각 연결 요소의 크기와 같다. 똑같이 DFS나 BFS를 사용해서 구할 수 있다.

 

3. 2에서 구한 값을 사용하여 모든 벽에 대해 해당 벽을 제거했을 때 얻을 수 있는 방의 크기를 구한다.

 하나의 벽을 제거하면 두 칸이 이어지므로 최대 두 개의 방이 하나로 합쳐질 수 있다. 따라서 벽 하나를 제거했을 때 얻어지는 방의 크기는 이어지는 두 칸이 속한 두 방의 크기를 합한 것과 같다. 2에서 구해둔 값을 사용하여 모든 벽에 대해 해당 벽을 제거했을 때 얻을 수 있는 방의 크기를 구한 뒤 그중 최댓값을 구한다.

반응형

---

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;

int N, M;
int board[50][50];
int visit[50][50];
int roomSize[2501];

int dr[] = {0, -1, 0, 1};
int dc[] = {-1, 0, 1, 0};

int DFS(int r, int c, int mark) {
    if (visit[r][c]) return 0;
    
    int ret = 1;
    visit[r][c] = mark;
    
    for (int i=0; i<4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
        if ((board[r][c] & (1 << i)) != 0) continue;
        
        ret += DFS(nr, nc, mark);
    }
    
    return ret;
}

piii solution() {
    int cnt = 0;
    int widestRoom = 0;
    int widestRoomWhenRemoveWall = 0;
    
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (!visit[i][j]) {
                cnt++;
                roomSize[cnt] = DFS(i, j, cnt);
                widestRoom = max(widestRoom, roomSize[cnt]);
            }
        }
    }
    
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            for (int k=0; k<4; k++) {
                int nr = i + dr[k];0
                int nc = j + dc[k];
                
                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                if ((board[i][j] & (1 << k)) == 0) continue;
                if (visit[i][j] == visit[nr][nc]) continue;
                
                int totalSize = roomSize[visit[i][j]] + roomSize[visit[nr][nc]];
                widestRoomWhenRemoveWall = max(widestRoomWhenRemoveWall, totalSize);
            }
        }
    }
    
    return {cnt, {widestRoom, widestRoomWhenRemoveWall}};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> M >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            cin >> board[i][j];
        }
    }
    
    piii res = solution();
    int numberOfRooms = res.first;
    int widestRoom = res.second.first;
    int widestRoomWhenRemoveWall = res.second.second;
    
    cout << numberOfRooms << "\n";
    cout << widestRoom << "\n";
    cout << widestRoomWhenRemoveWall << "\n";

    return 0;
}