백준 2234번 성곽 (C++)

문제 링크 : https://www.acmicpc.net/problem/2234

2234번: 성곽

문제 요약

 

1.  m*n사이즈의 배열에 성곽에 대한 정보가 주어집니다. 

2. 성곽[i][j]에는 해당 위치에 대한 벽의 정보가 주어집니다. 서쪽에 벽이 있을때는 1, 북쪽은 2, 동쪽은 4, 남쪽은 8입니다.

또한 성곽[i][j]는 최소 0, 최대 15의 값을 가집니다.

3. 이 성에 있는 방의 개수, 가장 넓은 방의 넓이, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 출력하세요.

 

핵심 포인트

BFS개념에 '비트마스크' 개념을 활용해야합니다.

여기서 주로 활용될 비트마스크의 개념은 다음과 같습니다.

1. << (Left Shift 연산)

ex : 1<<0 = 1
ex : 1<<1 = 2
ex : 1<<2 = 4

2. & (AND 연산) 

ex :   0101
     & 1001
     ------
       0001

 

문제 풀이

 

1. 필요한 변수를 선언하고 값을 입력받습니다.

배열을 입력받는 과정은 간단하므로 설명을 생략합니다.

단, 전역변수 활용이 중요하므로 아래와 같이 전역 변수를 선언합니다.

int m,n,ny,nx,y,x,my[]={0,-1,0,1},mx[]={-1,0,1,0};
int arr[MAX][MAX],ch[MAX][MAX],map[MAX][MAX]; 
// arr = 성곽배열, ch = 이어진 방을 구분, map = 방의 최대 넓이
int color=0, num=0, temp, largeroom, largeroom2;
// color = 이어진 방을 구분할 변수, num = 이어진 방의 넓이를 구분할 변수
//largeroom = 가장 넓은 방, largeroom2 = 벽을 부쉈을때 가장 넓은 방

struct pa{
    int yy;
    int xx;
};
queue<pa> q;
// BFS에 쓰일 Queue이며, 전역변수로 선언하는 것이 핵심입니다.

 

2. 방의 넓이와 가장 넓은 방의 크기를 구합니다.

void firstAndSecond(){
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(ch[i][j]==0){ // 1
                color++; // 2
                num = 1; // 3
                ch[i][j] = color; // 4 
                q.push({i,j}); // 5
                for(int k=0; k<4; k++){ // 6
                    y=i+my[k];
                    x=j+mx[k];
                    if(y<0||y>=m||x<0||x>=n) continue; // 7
                    if(ch[y][x]!=0) continue; // 8
                    temp = 1<<k; // 9
                    if(arr[i][j]&temp) continue; // 10
                    bfs(y,x); // 11
                }
                while(!q.empty()){
                    y = q.front().yy;
                    x = q.front().xx;
                    q.pop();
                    map[y][x] = num;
                }
                if(largeroom<num) largeroom = num;
            }
        }
    }

}

(1) ch배열은 연결된 방을 표시해주는 배열입니다. 0일 경우 아직 방문하지 않은 방이므로, 조건절에 들어갑니다.

(2) color을 +1합니다. color은 전역변수이며, 0으로 초기화되어있습니다. 연결된 방을 표시해줄 변수이며, 결국 color는 성에 있는 방의 갯수를 의미합니다.

(3) num은 1로 선언합니다. 전역변수로 선언되어있으며, 방의 넓이를 측정할 값입니다.

(4) 현재 방문한 방을 color변수로 구분해줍니다.

(5) 큐에 현재 방문한 방을 넣어줍니다.

(6) 4방위로 for문을 돌려서

-> 방문 범위를 초과할 경우 continue합니다.

-> 이미 방문한 방은 continue합니다.

-> 현재 동서남북(1,2,4,8)값을 비트마스크를 통해 구합니다. 1<<0일 경우, 값은 1이 됩니다.

-> 새로운 위치를 방문하기 이전, 현재 위치의 성벽값이 temp를 가지고있다면, 새로운 위치는 벽으로 막혀서 방문할 수 없음을 뜻합니다. continue를 합니다.

-> 만약 위의 모든 과정을 통과했다면 방문할 수 있는 위치이므로, bfs를 진행합니다.

 

3. BFS코드입니다.

void bfs(int y, int x){
    num++;
    ch[y][x] = color;
    q.push({y,x});
    for(int k=0; k<4; k++){
        ny=y+my[k];
        nx=x+mx[k];
        if(ny<0||ny>=m||nx<0||nx>=n) continue;
        if(ch[ny][nx]!=0) continue; // 이미 방문함
        temp = 1<<k;
        if(arr[y][x]&temp) continue; // 벽
        bfs(ny,nx);
    }
}

한 가지 눈여겨볼 점은, queue와 num이 전역변수로 선언되어있기 때문에 저렇게 값을 저장할 수 있다는 점입니다.

나머지는 2번 코드와 흡사한 점이 많으므로, 자세한 설명은 생략합니다.

 

4. 다시 2번코드로 돌아옵니다.

void firstAndSecond(){
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(ch[i][j]==0){
                color++;
                num = 1; // 방의 넓이
                ch[i][j] = color;
                q.push({i,j});
                for(int k=0; k<4; k++){
                    y=i+my[k];
                    x=j+mx[k];
                    if(y<0||y>=m||x<0||x>=n) continue;
                    if(ch[y][x]!=0) continue;
                    temp = 1<<k;
                    if(arr[i][j]&temp) continue;
                    bfs(y,x);
                }
                while(!q.empty()){ // 1
                    y = q.front().yy; // 2 
                    x = q.front().xx; 
                    q.pop();
                    map[y][x] = num; // 3
                }
                if(largeroom<num) largeroom = num; // 4
            }
        }
    }

}

(1) BFS를 통해 현재 i,j위치와 연결된 모든 방들을 큐에 저장했습니다. 때문에 큐가 빌때까지 while문을 진행합니다.

(2) 현재 위치를 각각 y,x에 저장하고 큐를 pop합니다.

(3) map[y][x]에 누적된 연결된 방의 크기를 저장합니다.

(4) 만약 largeroom보다 num이 크다면, 그 값이 가장 넓은 방의 크기입니다. 해당 값을 저장합니다.

 

5. 다음은 벽을 1개 부쉈을때를 가정하고 가장 넓은 방의 크기를 구하는 코드입니다.

void third(){
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(arr[i][j]!=-1){ // 1
                arr[i][j]=-1; // 2
                for(int k=0; k<4; k++){ // 3
                    y=i+my[k]; 
                    x=j+mx[k];
                    if(y<0||y>=m||x<0||x>=n) continue; // 4
                    if(ch[y][x]==-1) continue; // 5
                    temp = 1<<k; // 6
                    if(arr[i][j]&temp){ // 7
                        if(map[y][x]+map[i][j]>largeroom2&&ch[i][j]!=ch[y][x]) largeroom2 = map[y][x]+map[i][j];
                    }
                }
            }
        }
    }
}

(1) arr[i][j]값이 -1이 아니라면, 아직 벽을 부수지 않은 방이라는 뜻입니다. 조건절에 들어갑니다.

(2) arr[i][j]의 값을 -1로 바꿔줍니다.

(3) 4방위로 for문을 돌립니다.

(4) 새로운 위치가 방문가능범위를 초과할경우, continue를 합니다.

(5) 새로운 위치의 arr배열값이 -1일 경우, 이미 방문했던 곳이라는 뜻입니다. continue를 합니다.

(6) 현재 동서남북(1,2,4,8)값을 구합니다.

(7) 현재 위치와 temp값을 &연산자로 계산하여 true가 나올 경우, 현재 위치에 temp값이 있다는 뜻입니다. 즉, 벽이 있다는 의미입니다.

-> 때문에 벽을 부수고 새로운 위치와 현재 위치의 방을 합친 크기가 largeroom2보다 클 경우, 새로운 값을 갱신해주면 됩니다.

-> 여기서 ch[i][j]!=ch[y][x]가 포인트입니다. 이 조건은 다음과 같은 케이스를 방지합니다.

A와 B의 경우, 벽으로 막혀있지만 결론적으로 하나의 방입니다.

 

6. 정답을 출력합니다.

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    firstAndSecond();
    third();
    cout << color << "\n" << largeroom << "\n" << largeroom2 << "\n";
    return 0;
}

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define MAX 51

using namespace std;
// m = 세로, n = 가로
int m,n,ny,nx,y,x,my[]={0,-1,0,1},mx[]={-1,0,1,0},arr[MAX][MAX],ch[MAX][MAX],map[MAX][MAX],color=0, num=0, temp, largeroom, largeroom2;
struct pa{
    int yy;
    int xx;
};
queue<pa> q;

void input(){
    cin >> n >> m;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++) cin >> arr[i][j];
    }
}

void bfs(int y, int x){
    num++;
    ch[y][x] = color;
    q.push({y,x});
    for(int k=0; k<4; k++){
        ny=y+my[k];
        nx=x+mx[k];
        if(ny<0||ny>=m||nx<0||nx>=n) continue;
        if(ch[ny][nx]!=0) continue; // 이미 방문함
        temp = 1<<k;
        if(arr[y][x]&temp) continue; // 벽
        bfs(ny,nx);
    }
}

void firstAndSecond(){
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(ch[i][j]==0){
                color++;
                num = 1; // 방의 넓이
                ch[i][j] = color;
                q.push({i,j});
                for(int k=0; k<4; k++){
                    y=i+my[k];
                    x=j+mx[k];
                    if(y<0||y>=m||x<0||x>=n) continue;
                    if(ch[y][x]!=0) continue; // 이미 방문함
                    temp = 1<<k;
                    if(arr[i][j]&temp) continue; // 벽
                    bfs(y,x);
                }
                while(!q.empty()){
                    y = q.front().yy;
                    x = q.front().xx;
                    q.pop();
                    map[y][x] = num;
                }
                if(largeroom<num) largeroom = num;
            }
        }
    }

}

void third(){
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(arr[i][j]!=-1){
                arr[i][j]=-1;
                for(int k=0; k<4; k++){
                    y=i+my[k];
                    x=j+mx[k];
                    if(y<0||y>=m||x<0||x>=n) continue;
                    if(arr[y][x]==-1) continue; // 이미 방문함
                    temp = 1<<k;
                    if(arr[i][j]&temp){
                        if(map[y][x]+map[i][j]>largeroom2&&ch[i][j]!=ch[y][x]) largeroom2 = map[y][x]+map[i][j];
                    }
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    firstAndSecond();
    third();
    cout << color << "\n" << largeroom << "\n" << largeroom2 << "\n";
    return 0;
}