BOJ 14502 연구소

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

14502번: 연구소

문제 해결전략

 

연구소 문제는 DFS와 BFS를 혼합한 문제이다.

문제 해결의 순서

DFS를 통해 map의 빈 공간에 벽 3개 배치 -> temp 배열에 map을 복사 -> map에 바이러스 퍼뜨리기 -> 안전지대 갯수 세기 -> map에 temp를 복사 -> 다시 DFS를 통해 벽 3개 배치 -> 최대 안전지대 갯수 갱신

 

소스

#include <iostream>
#include <queue>
using namespace std;
#define endl "\n"
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int map[8][8];
int n, m;
int totalNum = -1;

struct virus{
    int y, x;
};
virus v[10];

void check(){
    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(map[i][j]) continue;
            cnt++;
        }
    }
    totalNum = max(totalNum, cnt);
}

void copy(int tmp[8][8], int origin[8][8]){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            tmp[i][j] = origin[i][j];
        }
    }
}

void bfs(){
    queue<pair<int, int>> q;
    for(int i = 0; i < 10; i++){
        if(map[v[i].y][v[i].x] != 2) break;
        q.push({v[i].y, v[i].x});
    }
    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(ny < 0 || ny >= n || nx < 0 || nx >= m || map[ny][nx]) continue;
            map[ny][nx] = 2;
            q.push({ny, nx});
        }
    }
    check();
}

void dfs(int cnt){
    if(cnt == 3){
        int temp[8][8];
        copy(temp, map);
        bfs();
        copy(map, temp);
        return;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(map[i][j]) continue;
            map[i][j] = 1;
            dfs(cnt + 1);
            map[i][j] = 0;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    int idx = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> map[i][j];
            if(map[i][j] == 2){
                v[idx].y = i; v[idx].x = j;
                idx++;
            }
        }
    }
    dfs(0);
    cout << totalNum;
}