[BOJ/백준] 14502번 - 연구소 (C++)

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

14502번: 연구소

 

요즘 해킹보다는 백준푸는게 더 재밌어서 PS를 하고있다. 풀다가 가끔씩 재밌었던 문제나 삽질했던 문제들을 블로그에 포스팅할 계획이다.

 

 

일단 이 문제에서는 2가 바이러스고 1이 벽이고 0이 빈 공간이다. 입력으로 바이러스와 벽, 빈공간이 있는 맵이 주어지고 여기서 벽 3개를 어떻게 더 세우면 인접한 빈 칸으로 퍼져나가는 바이러스의 확산을 최대한 막을 수 있냐고 물어보는 문제이다.

 

문제를 보자마자 가장 먼저 떠오르는 방법은 모든 경우의 수를 무식하게 완탐돌리는 것이다. 1이 3개 들어갈 수 있는 모든 조합을 전부 시도해보고 바이러스를 BFS나 DFS로 확산시켜보면서 빈 공간이 가장 많은 경우를 찾는 방법이다.

 

무조건 시간초과가 날듯한 시나리오였지만 N과 M의 범위가 8까지길래 잘하면 가능하겠다 싶어서 한번 시간복잡도를 계산해봤다.

 

먼저 입력으로 주어질 수 있는 맵의 최대 크기가 8*8 = 64니까 N = 64로 두고 계산을 해보겠다.

일단 1이 3개 들어가는 모든 조합의 경우의 수는 N(N-1)(N-2)/(3*2*1)이 되는데 빅오 표기법은 최고차항 이외에는 다 무시해버리므로 사실상 O(N^3)이 된다. 그리고 1을 3개 넣어볼 때마다 DFS나 BFS로 바이러스를 확산시켜보니까 저기다 N을 곱해줘서 O(N^4)가 된다. 확산시킨 후에는 빈 공간을 체크하는데 이것도 N만큼의 연산이 필요하니까 최종적으로는  O(2N^4)가 된다. 이론상으로는 이러한데 실제로 코드를 짤때는 DFS나 BFS돌릴때마다 방문체크하는 배열도 초기화 해줘야되니까 최종적으로는 O(3N^4)가 된다.

 

 

PS할때는 1초에 1억회라는 가정을 두고 시간을 계산하는데 문제에서 주어진 시간은 2초인데 1초가 안되는 시간이 걸린다..?

 

일단 되는건 확인했으니 빅오 표기법에서 생략한 항들까지 정확한 수치로 다시 계산해보면 (3N^2)(N-1)(N-2)/(3*2*1)이러한 식이 도출되고

 

 

엄청 널널하다. 그러면 바로 코드를 짜보겠다.

 

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

using namespace std;

int map[8][8];
bool v[8][8];
int n, m;

void dfs(int i, int j){
    if(i >= 0 && j >= 0 && i < n && j < m && !v[i][j] && (!map[i][j] || map[i][j] == 2)){
        v[i][j] = true;
        dfs(i+1, j);
        dfs(i-1, j);
        dfs(i, j+1);
        dfs(i, j-1);
    }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int c = 0, c1 = 0, w, x, y, z;
    cin >> n >> m;
    vector<pair<int, int>> b;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> map[i][j];
            if(map[i][j] == 2) b.push_back(make_pair(i, j));
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(i >= n-1 && j >= m-2) break;
            if(map[i][j]) continue;
            for(int k = 0; k < n; k++){
                for(int l = 0; l < m; l++){
                    if(k <= i && l <= j) continue;
                    if(map[k][l]) continue;
                    for(int o = 0; o < n; o++){
                        for(int p = 0; p < m; p++){
                            if(o <= k && p <= l) continue;
                            if(map[o][p]) continue;
                            map[i][j] = 1;
                            map[k][l] = 1;
                            map[o][p] = 1;
                            for(int q = 0; q < b.size(); q++)
                                dfs(b[q].first, b[q].second);
                            for(int q = 0; q < n; q++){
                                for(int r = 0; r < m; r++){
                                    if(!map[q][r] && !v[q][r]) c1++;
                                    v[q][r] = false;
                                }
                            }
                            c = c<c1?c1:c;
                            c1 = 0;
                            map[o][p] = 0;
                        }
                    }
                    map[k][l] = 0;
                }
            }
            map[i][j] = 0;
        }
    }
    cout << c;

    return 0;
}

 

 

무식하게 6중 for문 돌려서 했다. map에 1을 3개씩 가능한 조합을 전부 대입해보는 코드이다.

 

 

아까 시간복잡도 계산했을때 800만 정도가 나왔는데 시간을 보면 비슷한 수치가 나왔다.

 

N과 M의 범위가 매우 작아서 가능한 풀이였다.