[Gold 4] 14502 연구소

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

 

이 문제는 BFS를 사용하면 해결할 수 있다.

 

연구소에는 벽 3개를 세울 수 있고, 벽에 따라 바이러스가 퍼지는 수는 상이하다.

 

따라서 벽을 3개 세우고, BFS를 통해 바이러스를 퍼지게 하면 된다.

바이러스가 퍼지면 2가 배열을 채우게 되므로 새로운 배열이 필요하다.

또한, 벽을 세우게되면 1이 배열을 채우게 되므로 새로운 배열이 필요하다.

따라서 temp배열을 통해 벽을 세우고, spread 배열을 통해 바이러스를 퍼트린다.

 

벽을 세우는 과정은 제귀 형식으로 해결하였다.

원본 배열을 순차적으로 순회하여 값이 0인 경우 먼저 temp 배열에 원본의 값을 복사시킨다. 

이후, 복사된 배열에 벽을 세운다.(1로 값을 변경)

1개의 벽에 대해 모든 경우를 완료하였다면 다음 벽을 찾도록 한다.

for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(graph[i][j] == 0){
                copyGraph(temp, graph);
                temp[i][j] = 1;
                dfs(1);
                temp[i][j] = 0;
            }
        }
    }

 

dfs라는 함수는 1개의 벽에 대해 다음 벽을 세울 경우를 찾는 함수이다.

다음 벽은 위에서 1개의 벽을 찾는 경우와 동일하게 순차적으로 배열을 순회하는 것이다.

위와 다른 것은 원본 배열을 순회하는 것이 아닌 복사된 배열을 순회하는 것이다.

벽을 3개 세우는 것을 알 수 있는 방법은 count 변수를 통해 3인 경우 BFS를 호출하도록 하면 된다.

void dfs(int num){
    if(num == 3){
        bfs();
        return;
    }

    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(temp[i][j] == 0){
                temp[i][j] = 1;
                dfs(num + 1);
                temp[i][j] = 0;
            }
        }
    }

}

 

벽을 3개 세웠다면 BFS를 통해 바이러스를 퍼트려야한다.

이때 temp 배열에 바이러스를 퍼트리게된다면 또다른 경우의 벽을 세울 수 없을 것이다.

따라서 spread 배열에 temp 배열 속 값을 복사하고, BFS를 수행해야한다.

바이러스를 퍼트리는 시작 점은 바이러스의 값이 있는 위치이기 때문에

순차 탐색을 통해 바이러스를 찾아 위치를 큐에 삽입한다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int N, M;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int graph[8][8];
int answer = 0;
int temp[8][8];

void copyGraph(int a[8][8], int b[8][8]){
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++)
            a[i][j] = b[i][j];
    }
}

void bfs(){
    int spread[8][8];
    copyGraph(spread, temp);
    queue<pair<int,int>> q;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(spread[i][j] == 2)
                q.push({i,j});
        }
    }

    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;

        q.pop();
        for(int i = 0;i<4;i++){
            int uy = y + dy[i];
            int ux = x + dx[i];
            if(uy < 0 || uy >= N || ux < 0 || ux >=M)
                continue;
            
            if(spread[uy][ux] == 0){
                spread[uy][ux] = 2;
                q.push({uy,ux});
            }
        }
    }
    int cnt = 0;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(spread[i][j] == 0)
                cnt++;
        }
    }
    answer = max(answer, cnt);
}
void dfs(int num){
    if(num == 3){
        bfs();
        return;
    }

    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(temp[i][j] == 0){
                temp[i][j] = 1;
                dfs(num + 1);
                temp[i][j] = 0;
            }
        }
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>M;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++)
            cin>>graph[i][j];
    }
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(graph[i][j] == 0){
                copyGraph(temp, graph);
                temp[i][j] = 1;
                dfs(1);
                temp[i][j] = 0;
            }
        }
    }
    cout<<answer;
}