성곽 (feat. 백준, 2234번)

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

2234번: 성곽

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
struct Wall{
    bool up;        // false : 갈수없음, true : 갈수있음
    bool down;
    bool left;
    bool right;
};
int N, M, room_size;
Wall walls[50][50];
bool visit[50][50];
int bfs(){
    memset(visit, false, sizeof(visit));
    int cnt = 0;
    queue<pair<int, int>> q;
    for(register int i = 0, j, x, y, d, nx, ny; i < N; ++i)
        for(j = 0; j < M; ++j)
            if(!visit[i][j]){
                ++cnt;
                q.push(make_pair(i, j));
                visit[i][j] = true;   
                auto tmp = 0;    
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    x = p.first, y = p.second;
                    // up check
                    if(walls[x][y].up && x - 1 >= 0 && !visit[x - 1][y])
                        visit[x - 1][y] = true, q.push(make_pair(x - 1, y));
                    // down check
                    if(walls[x][y].down && x + 1 < N && !visit[x + 1][y])
                        visit[x + 1][y] = true, q.push(make_pair(x + 1, y));
                    // left check
                    if(walls[x][y].left && y - 1 >= 0 && !visit[x][y - 1])
                        visit[x][y - 1] = true, q.push(make_pair(x, y - 1));
                    // right check
                    if(walls[x][y].right && y + 1 < M && !visit[x][y + 1])
                        visit[x][y + 1] = true, q.push(make_pair(x, y + 1));
                    ++tmp;
                }
                room_size = max(room_size, tmp);
            }
    return cnt;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    room_size = 0;
    memset(walls, 0, sizeof(walls));
    cin >> M >> N;
    for(register int i = 0, j, v; i < N; ++i)
        for(j = 0; j < M; ++j){
            cin >> v;
            auto& wall = walls[i][j];
            wall.left = (v & 1) == 0 ? true : false;
            wall.up = (v & 2) == 0 ? true : false;
            wall.right = (v & 4) == 0 ? true : false;
            wall.down = (v & 8) == 0 ? true : false;
        }
    cout << bfs() << "\n" << room_size << "\n";
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < M; ++j){
            auto& wall = walls[i][j];
            if(!wall.up)
                wall.up = true, bfs(), wall.up = false;
            if(!wall.down)
                wall.down = true, bfs(), wall.down = false;
            if(!wall.left)
                wall.left = true, bfs(), wall.left = false;
            if(!wall.right)
                wall.right = true, bfs(), wall.right = false;
        }
    cout << room_size;
	return 0;
}
// *&)*@*

 

반응형

1. 한 지점에서 상,하,좌,우의 성벽으로 갈수 있거나 없거나에 따라 다음 지점으로 이동이 가능하므로 이를 bfs를 통해 알 수 있습니다.
2. 1번에 의해 방의 개수와 가장 넓은 방의 크기를 알 수 있습니다.
3. 모든 지점에 대해서 상,하,좌,우의 성벽으로 갈 수 없다면 각각에 대해 임시적으로 갈 수 있다는 조건을 주고 1번을 수행한다면 벽 하나를 제거했을때의 가장 넓은 방의 크기를 알 수 있습니다.