[백준][C++] 2234 성곽

www.acmicpc.net/problem/2234

2234번: 성곽

 

 

 

알고리즘 종류

    - BFS

    - 구현

 

 

 

사고 과정

    - 구해야 하는 항목은 3가지이다.

        * 방의 개수, 가장 넓은 방의 크기, 하나의 벽을 허물었을 때 가장 큰 방의 크기

 

    - 문제에서 제시해 주고 있듯이 비트 연산을 사용하면 쉽게 풀 수 있다. 

        * 간단하게 하는 방법을 알아보자.

            + 1은 0001, 2는 0010, 4는 0100, 8은 1000 이다.

            + 12는 1100이다. 위에서 1000과 0100의 합으로 만들 수 있다.

            + 11은 1011이다. 위에서 1000과 0010 그리고 0001의 합으로 만들 수 있다.

        

        * 그러면 어떤 값에서 우리가 원하는 값이 포함된 것을 어떻게 알 수 있을까? AND 연산을 사용하자

            + 12인 1100과 4인 0100를 AND 연산하면, 0100이 나온다.

            + 11인 1011과 8인 1000을 AND 연산하면, 1000이 나온다.

 

        * 문제에 어떻게 적용할까?

            + 4방향(1, 2, 4, 8)를 배열에 저장된 값(mat[i][j])과 AND 연산을 하면 벽이 있는지 알 수 있다.

 

    - 벽을 하나 허물어서 가장 큰 방의 크기는 어떻게 구할까?

        * 이중 for문으로 돌면서 벽이 있으면 부수고 BFS를 수행한다.

        * 더 빠른 방법을 찾아보았지만 알 수 없었다. 혹시, 이 글을 읽는 분 중에 아시는 분이 있다면, 알려주시면 감사하겠습니다.

 

 

 

구현(C++)

#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
int h, w;
int roomSize=0;
int roomCnt=0;
int largestRoomSize=0;
 
int mat[51][51];
int isVisited[51][51];
int dir[4][2] = {{0,-1}, {-1,0}, {0,1}, {1,0}};
 
 
bool isValid(int y, int x){
    return (y>=0 && y<h) && (x>=0 && x<w);
}
 
 
int bfs(int y, int x){
    queue<pair<int, int> > q;
    q.push({y, x});
    isVisited[y][x] = 1;
    int size = 1;
    
    while(!q.empty()){
        
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();
        
        for(int d=0; d<4; d++){
            int ny = cy + dir[d][0];
            int nx = cx + dir[d][1];
            
            if((mat[cy][cx] & 1<<d)) continue; // 현재 위치에서 이동할 방향에 벽이 있는가? 
            if(isVisited[ny][nx]) continue;
            if(!isValid(ny, nx)) continue;
            
            isVisited[ny][nx] = 1;
            size ++;
            q.push({ny, nx});
        }
    }
    
    return size;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> w >> h;
    
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> mat[i][j];
        }
    }
    
    // cout the num of room
    // largest room
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(isVisited[i][j]) continue;
            roomSize = max(roomSize, bfs(i,j));
            roomCnt ++;
        }
    }
    
    cout << roomCnt << endl;
    cout << roomSize << endl;
    
    // remove a wall
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            for(int d=0; d<4; d++){
                if((mat[i][j] & 1<<d)){
                    memset(isVisited, 0, sizeof(isVisited));
                    mat[i][j] -= 1<<d;
                    largestRoomSize = max(largestRoomSize, bfs(i, j));
                    mat[i][j] += 1<<d;
                }
            }
        }
    }
    
    cout << largestRoomSize << endl;
}

 

 

 

시행착오

    - 비트 연산을 제대로 사용해 본 적이 없었는데, 이 문제에서 사용해 볼 수 있었다.