백준 14502: 연구소

문제

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

문제를 보자마자 "아! 이거는 DFS나 BFS로 풀면 되겠다!" 라고 생각이 들어서 무작정 풀었다가 큰코를 다쳤습니다....

해당 문제를 푸는 과정은 다음과 같습니다.

1. 연구소 상황을 입력 받는다.
2. 받은 연구소 상황을 다른 배열에 복사한다.
3. 복사한 연구소에서 안전구역인 곳에 3개의 벽을 세운다.
4. 벽을 세운 상태에서 바이러스를 퍼트린다.
5. 다 퍼트린 후, 안전 구역의 수를 센다.
6. 구역의 수를 기존의 저장값과 비교하여 최대인지 확인한다.
7. 모든 벽을 세울 수 있는 경우를 계산 할 때까지 3번과정부터 반복한다.

해결 방식을 세우는것은 간단 하였으나... 3번 과정에서 많은 시간을 투자하게 되었습니다...

3개의 벽을 세울때, 입력 받는 연구소의 크기가 작아 세울 수 있는 모든 방법을 계산해도 괜찮습니다. 

따라서 모든 경우의 수를 구하는 방식이므로 지도를 복사해야 합니다.(기존의 지도를 기억하고 있어야합니다!!)

바이러스를 퍼트릴 때에도 따로 저장을 해두었습니다.

바이러스가 퍼지는 경우에는 다른 DFS,BFS 문제들과 비슷합니다.

코드

#include <cstdio>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int lab[8][8];
int tempLab[8][8];
int n,m;
int ans = 0;
 
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
 
//지도 복사
void mapCopy(int (*a)[8], int (*b)[8]){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = b[i][j];
        }
    }
}
//바이러스 퍼트리기(BFS)
void virusSpread(){
    //SpreadLab은 3개의 벽으로 막은 후 바이러스가 퍼졌을 때의 연구소의 상황을 저장하는곳.
    int SpreadLab[8][8];
    mapCopy(SpreadLab, tempLab);
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (SpreadLab[i][j] == 2)
                q.push(make_pair(i, j));
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            //연구소 범위 안에 감염되지 않은 영역만 오염시킬 수 있다.
            if(0<=nx && nx<n && 0<=ny && ny<m){
                if(SpreadLab[nx][ny] == 0){
                    SpreadLab[nx][ny] = 2;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
    //연구소에 오염되지 않은 부분 체크.
    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(SpreadLab[i][j] == 0)
                cnt+=1;
        }
    }
    ans = max(ans, cnt);
}
 
//벽 세우기(재귀호출 사용)
void wall(int cnt){
    //3개의 벽이 세워졌을 때, 바이러스를 퍼트린다.
    if(cnt == 3){
        virusSpread();
        return;
    }
    //벽 세우는 부분.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(tempLab[i][j]==0){
                tempLab[i][j] = 1;
                wall(cnt+1);
                //모든 경우의 수를 넣어야하므로 기존의 1을 0으로 바꾸어주는 역활
                tempLab[i][j] = 0;
            }
        }
    }
}
 
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d", &lab[i][j]);
        }
    }
    //연구소에서 0인 부분을 모두 벽을 세워야 하므로 다음과 같이 진행.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(lab[i][j] == 0){
                mapCopy(tempLab,lab);
                tempLab[i][j] =1;
                wall(1);
                tempLab[i][j] = 0;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}