[백준 / C++] 14502번 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

문제요약

격자에 바이러스가 위치한 좌표, 벽의 좌표가 표시되어있다. 벽을 3개 세워서 바이러스가 퍼지지 않는 곳의 최대넓이를 구하라.

문제해결

시뮬레이션 단계에 따라 각각 그래프 순회를 해야한다.

먼저 주어진 격자의 정보를 입력 받고, 벽을 3개 세울 때는 원본정보가 변하지 않게 다른 격자에다가 복사를 한 뒤 시뮬레이션을 한다.
벽을 시뮬레이션할 때는 DFS를 적용하였다.
벽을 다 세운뒤에는 바이러스 확산을 시뮬레이션하는데 BFS를 적용하였고, 먼저 바이러스의 위치들을 큐에 넣어준뒤 바이러스 확산을 BFS로 시뮬레이션하였다.
마지막에는 완전탐색을 통해 안전구역을 카운트 하였다.

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

using namespace std;

              // 동 남 서 북
vector<int> di = {0, 1, 0, -1};
vector<int> dj = {1, 0, -1, 0};

int N, M;
int world[8][8] = {0};
int test_world[8][8] = {0};
int ans = 0;

int count_safe(){
    int exam_world[8][8] = {0};
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            exam_world[i][j] = test_world[i][j];
        }
    }

    // 바이러스 확산
    queue<pair<int,int>> q;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(exam_world[i][j] == 2) q.push(make_pair(i, j));
        }
    }
            
    while(!q.empty()){
        auto p = q.front();
        int cur_i = p.first;
        int cur_j = p.second;
        q.pop();

        for(int d=0; d<4; d++){
            int next_i = cur_i + di[d];
            int next_j = cur_j + dj[d];
            if(next_i >=0 && next_i<N && next_j >=0 && next_j<M){
                if(exam_world[next_i][next_j] == 0){
                    exam_world[next_i][next_j] = 2;
                    q.push(make_pair(next_i, next_j));
                }
            }
        }
    }

    // 안전지역 카운트
    int area = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(exam_world[i][j]==0) area++;
        }
    }

    return area;
}

void make_wall(int start_i, int start_j, int count){
    if(count == 3){
        ans = max(ans, count_safe());
        return;
    }
    else{
        for(int i=start_i; i<N; i++){
            for(int j=start_j; j<M; j++){
                if(test_world[i][j]) continue;

                test_world[i][j] = 1;
                // make_wall(i, j, count-1);
                make_wall(0, 0, count+1);

                test_world[i][j] = 0;
            }
        }
    }
}

int main(){
    cin >> N >> M;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> world[i][j];
        }
    }

    for(int start_w_i=0; start_w_i<N; start_w_i++){
        for(int start_w_j=0; start_w_j<M; start_w_j++){
            // 벽을 세웠던 곳이거나 세울 수 없는 곳이면 continue
            if(world[start_w_i][start_w_j]) continue;
            
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    test_world[i][j] = world[i][j];
                }
            }   

            // 벽 세우기
            test_world[start_w_i][start_w_j] = 1;
            // make_wall(start_w_i, start_w_j, num_wall);
            make_wall(0, 0, 1);
            test_world[start_w_i][start_w_j] = 0;
        }
    }

    cout << ans;

}