14502_연구소

14502_연구소

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

1. 입력값 받기

2. 초기 바이러스의 위치를 저장

3. 벽세우기

   • 벽은 DFS를 이용.

   • 벽의 수가 3이면 바이러스를 퍼트린다.

4. 바이러스를 퍼트린 후 다시 벽을 세워야 하므로 배열을 복사한다.(visited에 저장)

   • BFS를 이용하여 바이러스를 퍼트린다.

   • 안전영역의 수를 센다.

   • if( 안전영역 > max) max = 안전영역

5. max값을 출력한다.

//
//  14502_연구소.cpp
//  cpp
//
//  Created by 박종훈 on 2018. 6. 11..
//  Copyright © 2018년 박종훈. All rights reserved.
//
​
#include <stdio.h>
#include <iostream>
#include <queue>
​
using namespace std;
​
int map[9][9];
int visited[9][9];
int N,M;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int maxi=0;
​
struct Pos {
    int x;
    int y;
};
​
queue<Pos> q;
​
void initVisited(){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            visited[i][j] = map[i][j];
        }
    }
}
​
int cntSafe(){
    int cnt=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(visited[i][j]==0) cnt++;
        }
    }
    return cnt;
}
​
void goVirus(){
    
    initVisited();
    queue<Pos> temp = q;
    int value;
    
    while (!temp.empty()) {
        int x = temp.front().x;
        int y = temp.front().y;
        temp.pop();
        for(int i=0;i<4;i++){
            Pos temp2;
            temp2.y = y+dy[i];
            temp2.x = x+dx[i];
            if(temp2.x < 0 || temp2.y <0 || temp2.x > M || temp2.y > N) {}
            else if(visited[temp2.y][temp2.x]==0){
                temp.push(temp2);
                visited[temp2.y][temp2.x]=2;
            }
        }
    }
    
    value = cntSafe();
    if(value > maxi) maxi = value;
}
​
void buildWall(int cnt){
    
    if(cnt==3){
        goVirus();
        return;
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]==0){
                map[i][j]=3;
                buildWall(cnt+1);
                map[i][j]=0;
            }
            
        }
    }
    
}
​
int main() {
    Pos p;
    scanf("%d %d", &N,&M);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf("%d", &map[i][j]);
            if(map[i][j] ==2 ) {
                p.y = i;
                p.x = j;
                q.push(p);
            }
            
        }
    }
    
    buildWall(0);
    cout << maxi;
    
}
​