BOJ 14502 - 연구소 / C++

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

14502번: 연구소

 

 

풀이

벽 3개를 세울 수 있는 경우의 수는 DFS로 완전탐색하고

그렇게 생성된 배열을 다시 BFS로 순회하며 바이러스를 퍼뜨리고 안전 영역을 세야한다.

 

우선, 입력 받은 배열을 돌며 0(빈 칸)을 발견하면 해당 지역부터 DFS를 시작한다.

해당 지역에 벽(1)을 세우고 DFS 카운트를 늘려준 뒤 다시 배열을 돌며 다음 0(빈 칸)을 찾는다.

이렇게 DFS의 카운트가 3이 되면 벽을 모두 세웠으므로 완성된 배열에서 BFS를 시작한다.

 

BFS는 완성된 배열을 돌며 2(바이러스)가 있는 위치를 큐에 저장해놓고

큐에서 상하좌우로 이동하며 0(빈 칸)을 2(바이러스)로 바꿔놓는 방식으로 진행된다.

BFS가 완료되면 spread 배열에 바이러스가 퍼진 상태가 완성된다.

이제 빈칸을 모두 세서 정답을 갱신해주면 된다.

 

코드

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };

int n, m, ans = 0;
int arr[8][8];
int copiedArr[8][8];

bool isInside(int y, int x){
    if(y >= 0 && x >= 0 && y < n && x < m) return true;
    else return false;
}

void BFS(){
    int spread[8][8];
    queue<pair<int, int> > q;

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            spread[i][j] = copiedArr[i][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 ny = y + dy[i];
            int nx = x + dx[i];

            if(!isInside(ny, nx)) continue;
            
            if(spread[ny][nx] == 0){
                spread[ny][nx] = 2;
                q.push({ny, nx});
            }
        }
    }

    int tmp = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(spread[i][j] == 0) tmp++;
        }
    }

    ans = max(ans, tmp);
}

void DFS(int cnt){
    if(cnt == 3) {
        BFS();
        return;
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(copiedArr[i][j] == 0){
                copiedArr[i][j] = 1;
                DFS(cnt + 1);
                copiedArr[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 >> arr[i][j];
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(arr[i][j] == 0) {
                for(int a=0; a<n; a++){
                    for(int b=0; b<m; b++){
                        copiedArr[a][b] = arr[a][b];
                    }
                }

                copiedArr[i][j] = 1;
                DFS(1);
                copiedArr[i][j] = 0;
            }
        }
    }

    cout << ans;
}