[BFS]백준14502번 연구소

백준 14502번

연구소

처음 문제를 읽으면서 바이러스를 퍼트리는 건 bfs를 사용하면 될 거라고 생각했지만, 벽을 세우는 것은 어떻게 해야 할 지 잘 감이 오지 않았다. 벽을 세우는 것도 무언가 방법이 있을거라고 생각했는데, 검색을 통해 알아보니 결국 다 테스트해보는 것이 답이었다. 다만 어떻게 하면 벽을 다 테스트하는 것을 구현할지 잘 이해가 안갔는데, 재귀로 모든 벽을 다 테스트 해야 했다.

알고리즘은 다음과 같다.

1. 우선 입력으로 받은 지도를 순회하면서 0을 찾으면 벽을 세운다.
2. 재귀 함수를 호출하고 그 안에서 다시 지도를 순회하며 벽을 마저 세운다. (벽을 총 세 개 세워야 하기 때문에 세 개까지 세운다.)
3. 벽을 세 개 째 세우면 BFS를 사용해 바이러스를 퍼트리고 안전 구역의 크기를 구한다.

위 과정을 계속해서 반복한다.

지도에 있는 모든 0에 대해 세울 수 있는 모든 벽을 세우고 각 case에 대해 가능한 안전 구역의 크기를 구한다. 가장 큰 안전구역의 크기만 저장한다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int map[9][9]={0,};
int tmp[9][9];
int y_iter[4] = {1,0,-1,0};
int x_iter[4] = {0,1,0,-1};
int height, width;
int maxSafeArea=0;
int zero_count=0;
vector<pair<int,int> > virus;
void setWall(int n);
void spreadVirus();

int main(){
    cin >> height >> width;
    // 입력받기
    for(int i=0;i<height;i++){
        for(int j=0;j<width;j++){
            cin >> map[i][j];
            if(map[i][j]==2){
                virus.push_back(make_pair(i,j));
            }
            if(map[i][j]==0){
                zero_count ++;
            }

        }
    }
    for(int i=0;i<height;i++){
        for(int j=0;j<width;j++){
            if(map[i][j]==0){
                for(int y=0;y<9;y++){
                    for(int x = 0;x<9;x++){
                        tmp[y][x]=map[y][x];
                    }
                }
                tmp[i][j] = 1;
                setWall(1);
                tmp[i][j]=0;
            }
        }
    }

     cout << maxSafeArea << endl;
}

void setWall(int n){
    if(n==3){
        spreadVirus();
        return;
    }
    for(int i=0;i<height;i++){
        for(int j=0;j<width;j++){
            if(tmp[i][j]==0){
                tmp[i][j]=1;
                setWall(n+1); // tmp[i][j]를 최대로 놓음으로써 구할 수 있는 최대 안전구역을 구한다.
                tmp[i][j]=0; // 다시 원래대로 돌려놔야 한다. 
            }
        }
    }
}

void spreadVirus(){
    int vir[9][9];
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            vir[i][j] = tmp[i][j];
        }
    }
    int test;
    int scores = 0;
    bool visited[9][9] = {false,};
    for(int i=0;i<height;i++){
        for(int j=0;j<width;j++){
            if(vir[i][j]==2 && !visited[i][j]){
                queue<pair<int,int> > q;
                q.push(make_pair(i,j));
                visited[i][j]= true;
                while(!q.empty()){
                    pair<int,int> cur = q.front();
                    q.pop();
                    for(int k=0;k<4;k++){
                        int y = cur.first + y_iter[k];
                        int x = cur.second + x_iter[k];
                        if(y >=0 && y<height && x >= 0 && x <width){
                            if(vir[y][x]==0 && !visited[y][x]){
                                vir[y][x] = 2;
                                visited[y][x] = true;
                                q.push(make_pair(y,x));
                            }
                        }
                    }
                }

            }
        }
    }
    for(int i=0;i<height;i++){
        for(int j=0;j<width;j++){
            if(vir[i][j]==0){
                scores++;
            }
        }
    }
    maxSafeArea  = scores>maxSafeArea ? scores:maxSafeArea;
}