문제

  • 연구소의 지도가 주어집니다. (0 빈칸, 1 벽, 2 바이러스)

  • 전체 바이러스 중에서 m개의 바이러스만 활성화 시킵니다.

  • 바이러스는 인접한 4방향(위쪽, 오른쪽, 아래쪽, 왼쪽)으로만 이동 가능하며 빈칸만 지날 수 있습니다.

  • 비활성화 바이러스는 활성화 바이러스를 만나면 활성화 상태가 됩니다.

  • 지도의 빈칸에 모든 바이러스가 퍼지는 최소시간을 구하시오.

  • n(5 ≤ n ≤ 50) 연구소의 크기

  • m(5 ≤ m ≤ 10) 바이러스의 개수

  • 시간 제한 1초

  • 문제 링크


접근 과정

0. 문제 잘읽기

  • 비활성화 바이러스는 활성화 바이러스를 만나면 활성화 상태가 됩니다. - 저는 이 조건을 고려하지 않아서 많이 틀렸습니다.

1. 백트래킹

  • 최대 10개의 바이러스중 m개를 선택합니다. 이를 위해 재귀적인 방법을 사용해주었습니다.

2. BFS

  • 바이러스가 퍼지는 최소 시간을 계산해주기 위해 BFS를 사용했습니다.
  • 모든 간선의 가중치가 같을때 BFS는 최단경로를 찾아줍니다.

3. 시간 복잡도 계산

  • 최대 m개에 대해 선택하고 말고 2^m
  • BFS로 지도 전체 탐색 n^2
  • n(5 ≤ n ≤ 50) 연구소의 크기, m(5 ≤ m ≤ 10) 바이러스의 개수 이기 때문에 총 시간 복잡도는 2^m * n^2 = 1024 * 2500 = 256만 시간안에 풀 수 있습니다.

코드

1. C++

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

#define max_int 51
#define max_val 2147483647
using namespace std;

//시간 복잡도: O(2^m*n^2)
//공간 복잡도: O(n^2)
//사용한 알고리즘: 백트래킹, BFS
//사용한 자료구조: 큐

int n, m, a[max_int][max_int], check[max_int][max_int], result = max_val;

struct info{
    int x;
    int y;
};

vector<info> virus, pick;
queue<info> q;
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};

void bfs() {

    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx>=0 && nx<n && ny>=0 && ny<n){
                // 1) 벽은 지나갈 수 없습니다.
                // 2) 비활성화 된 바이러스는 활성화 바이러스를 만나면 활성화 됩니다.
                if(a[nx][ny] != 1 && check[nx][ny] == -1){
                    check[nx][ny] = check[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }

    bool isClear = true;
    int max_time = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(a[i][j] == 0){
                // 만약 빈칸인데 바이러스가 퍼지지 않았으면 실패입니다.
                if(check[i][j] == -1){
                    isClear = false;
                    break;
                }
                // 바이러스가 퍼졌으면 최대 시간을 갱신해줍니다.
                else{
                    max_time = max(max_time, check[i][j]);
                }
            }

        }
    }
    // 최소시간을 갱신해줍니다.
    if(isClear) result = min(result, max_time);
}

// 재귀를 통해 m개의 활성화 바이러스를 선택해줍니다.
void go(int idx){
    if(idx == virus.size()){

        if(pick.size() == m){

            // 선택한 m개의 바이러스를 큐에 넣어줍니다.
            for(int i=0; i<m; i++) q.push(pick[i]);

            // check 배열 초기화
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    check[i][j] = -1;
                }
            }

            // m개의 바이러스에 대해 시작을 0 으로 설정합니다.
            for(int i=0; i<pick.size(); i++){
                int x = pick[i].x;
                int y = pick[i].y;
                check[x][y] = 0;
            }

            // bfs 탐색을 통해 지도 전체에 바이러스가 퍼지는 최소 시간을 계산해줍니다.
            bfs();

        }
        return;
    }

    // 1) idx번째 바이러스 선택
    pick.push_back({virus[idx].x, virus[idx].y});
    go(idx+1);
    pick.pop_back();

    // 2) idx번째 바이러스를 선택하지 않고 지나감
    go(idx+1);
}

int main(){
    // 1. 문제를 입력받습니다.
    scanf("%d %d", &n, &m);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &a[i][j]);

            // 2. 바이러스일 경우 x, y를 따로 저장해줍니다.
            if(a[i][j] == 2) virus.push_back({i, j});
        }
    }

    // 3. 전체 바이러스에 대해 활성화 시킬 m개만 선택해줍니다.
    go(0);

    // 4. 결과를 출력합니다.
    if(result == max_val) result = -1;
    printf("%d\n", result);
}