14502 연구소

문제 링크

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

풀이

먼저 메인함수에서는 맵을 전부 돌면서 벽을 세울 수 있는 빈 칸(0)을 찾는다.
빈칸을 찾은 후에는 벽을 세운 후(1로 업데이트) 벽을 세워주는 walls(int x, int cnt)로 넘어간다.
walls에서는 맵을 돌면서 또 비어있는 칸을 찾아 벽을 세우고,, 벽이 3개가 될때까지 재귀함수를 돌면서 반복한다.
벽이 3개가 되면 바이러스를 퍼트리기 위해 spread()로 넘어간다.
spread()에서는 바이러스가 있는 칸(2)을 찾은 후 그 주변을 bfs로 탐색하며 빈 칸이 있을 경우 바이러스를 전파시킨다.(2로 업데이트)
전부 전파시킨 후에는 안전한 칸의 개수를 세어 기존의 ans와 비교한다.
새롭게 구한 safe 값과 기존의 ans 값을 비교하여 더 큰 값이 ans로 되게 한다.
그렇게 구한 ans를 출력하면 되는 문제이다.

삼성에 자주 나오는 시뮬레이션 문제..
난 시뮬레이션을 잘 못하기 때문에 조금 헤맸다.
복잡해 보여도 작은거부터 하다보면 풀린다
divide and conquer..잊지말자,,,ㅠㅠ

C++코드

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

using namespace std;

int N, M;
int map[8][8];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int ans = 0;

void spread(){
    int tmp[8][8];
    copy(&map[0][0], &map[0][0]+64, &tmp[0][0]);
    queue<pair<int, int>> q;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(tmp[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 && tmp[nx][ny] == 0){
                tmp[nx][ny] = 2;
                q.push(make_pair(nx, ny));
            }
        }
    }
    
    int safe = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(tmp[i][j] == 0)
                safe++;
        }
    }
    
    ans = max(safe, ans);
}

void walls(int x, int cnt){
    // 벽 세개 세웠으면 바이러스 퍼트리기로 넘어감
    if(cnt == 3){
        spread();
        return;
    }
    for(int i=x; i<N; i++){
        for(int j=0; j<M; j++){
            if(map[i][j] == 0){
                map[i][j] = 1;
                walls(i, cnt+1);
                map[i][j] = 0;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>N>>M;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>map[i][j];
        }
    }
    
    // 벽 세우기
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(map[i][j] == 0){
                map[i][j] = 1;
                walls(i, 1);
                map[i][j] = 0;
            }
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}