문제

• 연구소의 지도가 주어집니다. (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);
}

1) c++

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

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

int n, m, a[max_int][max_int], check[max_int][max_int], empty_cnt, cur_cnt, max_time, result = max_val;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { -1, 1, 0, 0 };

struct info {
	int x, y;
};

queue<info> q;
vector<info> v, pick;

int max(int a, int b) {
	return a > b ? a : b;
}

int min(int a, int b) {
	return a < b ? a : b;
}

void init() {
	cur_cnt = empty_cnt;
	max_time = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			check[i][j] = -1;
		}
	}
}

void bfs() {

	while (!q.empty()) {
		info cur = q.front();
		q.pop();

		int x = cur.x;
		int y = cur.y;

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

			if (nx < 1 || nx > n || ny < 1 || ny > n) continue;

			if (a[nx][ny] != 1 && check[nx][ny] == -1) {
				check[nx][ny] = check[x][y] + 1;

				if (a[nx][ny] == 0) {
					cur_cnt--;

					max_time = max(max_time, check[nx][ny]);
				}

				q.push({ nx, ny });
			}
		}
	}
}

void go(int idx) {
	if (idx >= v.size()) {

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

			for (auto cur : pick) {
				check[cur.x][cur.y] = 0;
				q.push(cur);
			}

			bfs();

			if (cur_cnt == 0) {
				result = min(result, max_time);
			}
		}

		return;
	}

	pick.push_back(v[idx]);
	go(idx + 1);
	pick.pop_back();

	go(idx + 1);
}

int main() {
	scanf("%d %d", &n, &m);

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

			if (a[i][j] == 0) empty_cnt++;
			else if (a[i][j] == 2) {
				v.push_back({ i, j });
			}
		}
	}

	go(0);

	if (result == max_val) result = -1;

	printf("%d\n", result);
};

2) java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static int max_val = 2147483647;
    public static int n, m, a[][], check[][], empty_cnt, cur_cnt, max_time, result = max_val, dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};
    public static ArrayList<Info> v = new ArrayList<>();
    public static Stack<Info> pick = new Stack<>();
    public static Queue<Info> q = new LinkedList<>();

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        a = new int[n+1][n+1];
        check = new int[n+1][n+1];

        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());

            for(int j=1; j<=n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());

                if(a[i][j] == 0) empty_cnt++;
                else if(a[i][j] == 2) {
                    v.add(new Info(i, j));
                }
            }
        }

        go(0);

        if(result == max_val) result = -1;

        System.out.println(result);
    }

    public static void go(int idx) {
        if(idx >= v.size()) {

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

                for(Info cur: pick) {
                    check[cur.x][cur.y] = 0;
                    q.add(cur);
                }

                bfs();

                if(cur_cnt == 0) {
                    result = min(result, max_time);
                }
            }

            return;
        }


        pick.add(v.get(idx));
        go(idx + 1);
        pick.pop();

        go(idx + 1);
    }

    public static void bfs() {

        while(!q.isEmpty()) {
            Info cur = q.poll();

            int x = cur.x;
            int y = cur.y;

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

                if(nx < 1 || nx > n || ny < 1 || ny > n) continue;

                if(a[nx][ny] != 1 && check[nx][ny] == -1) {
                    check[nx][ny] = check[x][y] + 1;

                    if(a[nx][ny] == 0) {
                        cur_cnt--;

                        max_time = max(max_time, check[nx][ny]);
                    }

                    q.add(new Info(nx, ny));
                }
            }
        }
    }

    public static int max(int a, int b) {
        return a > b ? a : b;
    }

    public static int min(int a, int b) {
        return a < b ? a : b;
    }

    public static void init () {
        cur_cnt = empty_cnt;
        max_time = 0;
        for(int i=0; i<=n; i++) {
            for(int j=0; j<=n; j++) {
                check[i][j] = -1;
            }
        }
    }

    public static class Info {
        int x, y;

        public Info(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

3) python3

from collections import deque


def bfs():
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 1 or nx > n or ny < 1 or ny > n:
                continue

            if a[nx][ny] != 1 and check[nx][ny] == -1:
                check[nx][ny] = check[x][y] + 1

                if a[nx][ny] == 0:
                    global cur_cnt, max_time
                    cur_cnt -= 1
                    max_time = max(max_time, check[nx][ny])

                q.append((nx, ny))


def init():
    global cur_cnt, max_time, check
    max_time = 0
    cur_cnt = empty_cnt
    check = [[-1 for _ in range(n+1)] for _ in range(n+1)]


def go(idx):
    if idx >= len(v):
        if len(pick) == m:
            init()

            for cur in pick:
                x, y = cur
                check[x][y] = 0
                q.append((x, y))

            bfs()

            if cur_cnt == 0:
                global result
                result = min(result, max_time)

        return

    pick.append((v[idx]))
    go(idx + 1)
    pick.pop()

    go(idx + 1)


n, m = map(int, input().split())
a = [[0 for _ in range(n + 1)]]
v = []
pick = []
check = []
q = deque()
empty_cnt = cur_cnt = 0
max_time = 0
result = max_val = 2147483647
dx = 0, 0, 1, -1
dy = -1, 1, 0, 0

for i in range(1, n+1):
    arr = [0] + list(map(int, input().split()))
    a.append(arr)

    for j in range(1, n+1):
        if arr[j] == 0:
            empty_cnt += 1
        elif arr[j] == 2:
            v.append((i, j))


go(0)

if result == max_val:
    result = -1

print(result)