[C++] 연구소3 (17142번)

연구소 3

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

 

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.25 초 (하단 참고)

512 MB

42013

11419

6810

25.549%

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 비활성 바이러스의 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

---

문제풀이

구현문제는 항상 시간이 오래걸린다. 엣지케이스를 찾기 너무 어렵기 때문이다..

우선 이 문제는 완전탐색을 사용하여 풀 수있는 문제이다. 최대 10C5 * 50 * 50 의 경우의 수가 존재한다.

10C5는 바이러스 10개중 5개를 순서없이 고르는 경우의 수고, 각 경우마다 배열을 완전탐색해야 하므로 위와같은 경우의 수가 도출된다.

 

크게 두 부분으로 나누어 구현하였다.

1. 활성화 시킬 바이러스를 고른다.

2. 고른 바이러스를 기준으로 전파시킨다.

 

활성화 시킬 바이러스를 고르는 과정은 DFS를 사용했다.

고른 바이러스를 vector에 넣고, 문제에 제시된 활성화 시킬 바이러스의 수만큼 vector의 길이가 길어지면 2번을 수행한다.

 

고른 바이러스를 기준으로 전파시키는 과정은 BFS를 사용했다.

문제에 무슨 기호 쓰고, 너무 복잡하게 생각하니 머리가 터질것 같았다.

그래서 나는 방문 기록을 이용해서 소요 시간을 저장하기로 정했다. 맨 처음 0과 소요시간이 0인경우가 겹쳐서 처리가 어려우므로, 소요시간을 1초부터 시작하도록 했고 나중에 1을 빼서 정답을 구하는데 사용하였다.

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

using namespace std;

int n, m;
int arr[50][50];
int answer = 99999999;

void dfs(int idx, vector<pair<int, int>> chosed, vector<pair<int, int>>& virus) {
    if(chosed.size() == m) {
        // visited에 해당 위치까지 오는데 걸린시간 + 1이 저장됨.
        int visited[50][50] = {0, };
        queue<pair<int, int>> q;

        for(int i=0; i<chosed.size(); i++) {
            // cout << chosed[i].first << " " << chosed[i].second << endl;
            q.push(chosed[i]);
            visited[chosed[i].first][chosed[i].second] = 1;
        }
        // cout << endl;

        int now_answer = 0;

        while(!q.empty()) {
            pair<int, int> p = q.front();
            if(arr[p.first][p.second] != 2) now_answer = max(now_answer, visited[p.first][p.second]-1);

            q.pop();

            // 해당 위치가 바이러스가 아니고, 소요 시간이 현재 정답과 같거나 크면 그대로 순회를 종료한다.
            // 이거 찾는데 몇시간 걸림. 처음에 arr[p.first][p.second] != 2 이걸 빼서
            // 비활성화된 바이러스까지 시간초 계산을 해버려 92%에서 틀렸음.
            if(arr[p.first][p.second] != 2 && visited[p.first][p.second] - 1 >= answer) return;

            int r[] = {0, 0, 1, -1};
            int c[] = {1, -1, 0, 0};
            for(int i=0; i<4; i++) {
                int dr = p.first + r[i];
                int dc = p.second + c[i];

                if(dr>=0 && dr<n && dc>=0 && dc<n && visited[dr][dc] == 0 && arr[dr][dc] != 1) {
                    visited[dr][dc] = visited[p.first][p.second] + 1;
                    q.push({dr, dc});
                }
            }
        }


        // 방문하지 않은 빈칸이 있을경우 그대로 중지한다.
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(arr[i][j] == 0 && visited[i][j] == 0) return;
            }
        }
        answer = min(answer, now_answer);
        return;
    }

    for(int i=idx; i<virus.size(); i++) {
        chosed.push_back(virus[i]);
        dfs(i+1, chosed, virus);
        chosed.pop_back();
    }
}

int main() {
    cin >> n >> m;
    vector<pair<int, int>> virus;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int tmp;
            cin >> tmp;
            arr[i][j] = tmp;
            if(tmp == 2) {
                virus.push_back({i, j});
            }
        }
    }
    vector<pair<int, int>> v;
    dfs(0, v, virus);

    if(answer == 99999999) cout << -1;
    else cout << answer;
    return 0;
}