백준 17142번 <연구소 3>

백준 알고리즘 17142번

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

17142번: 연구소 3

---

17142번

바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 

승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

 

연구소의 크기는 N * N인 정사각형이며, 연구소는 빈 칸, 벽, 바이러스로 이루어져 있다.

활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스는 활성 바이러스로 변한다.

 

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

 

입력으로 첫 줄에 연구소의 크기 N과 활성 상태로 변경할 바이러스의 개수 M이 주어진다.

그 다음 줄부터 N개의 줄에 걸쳐 연구소의 상태가 주어진다. (0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다.)

 

출력으로 모든 빈 칸이 바이러스가 되는 최소 시간을 구해 출력하면 된다.

---

문제 해결

이 문제는 먼저 2의 위치 중에서 M개를 골라서 바이러스를 각각 퍼뜨려 봐야 한다.

 

2의 개수는 최대 10이기 때문에 조합의 값이 가장 큰 경우인 10C5가 252이기 때문에 계산이 가능하다.

2의 위치 중에서 M개를 골라서 활성 상태임을 표시하기 위해 값을 3으로 만들어주고 (visit 체크를 따로 해주지 않아도 된다.) 큐에 넣는다. 이를 가지고 bfs를 진행한다. 이때, 이미 활성 바이러스이거나 벽인 경우는 그냥 넘어간다.

 

모든 빈 칸에 바이러스가 있는지 확인하는 것은 0이 있는지 없는지만 보면 된다.

---

코드

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[][] Map;
	static int N, M, min_value;
	static Tuple[] select;
	static ArrayList<Tuple> virus;
	static int[] di = { 1, -1, 0, 0 };
	static int[] dj = { 0, 0, 1, -1 };

	static class Tuple {
		int i, j;

		public Tuple(int i, int j) {
			super();
			this.i = i;
			this.j = j;
		}

		@Override
		public String toString() {
			return "Tuple [i=" + i + ", j=" + j + "]";
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		Map = new int[N][N];
		virus = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				Map[i][j] = sc.nextInt();
				if (Map[i][j] == 2) {
					virus.add(new Tuple(i, j));
				}
			}
		} // end input

		if (check(Map)) { // 처음부터 모두 바이러스인 경우
			System.out.println(0);
			System.exit(0);
		}

		min_value = Integer.MAX_VALUE;
		select = new Tuple[M];
		combination(0, 0);

		if (min_value == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(min_value);
		}

	}

	static void combination(int cnt, int start) {
		if (cnt == M) {
			bfs();
			return;
		}
		for (int i = start; i < virus.size(); i++) {
			select[cnt] = virus.get(i);
			combination(cnt + 1, i + 1);
		}
	}

	static void bfs() {
		int[][] copy = deepcopy(Map);
		Queue<Tuple> q = new ArrayDeque<>();
		for (int k = 0; k < M; k++) {
			q.add(select[k]);
			copy[select[k].i][select[k].j] = 3;
		}
		int time = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int p = 0; p < size; p++) {
				Tuple tp = q.poll();
				for (int k = 0; k < 4; k++) {
					int ni = tp.i + di[k];
					int nj = tp.j + dj[k];
					if (ni < 0 || nj < 0 || ni >= N || nj >= N) {
						continue;
					}
					if (copy[ni][nj] == 3 || copy[ni][nj] == 1) {
						continue;
					}

					q.add(new Tuple(ni, nj));
					copy[ni][nj] = 3;
				}
			}
			if (check(copy)) {
				min_value = Math.min(min_value, time + 1);
				break;
			}
			time++;
		}
	}

	static void print(int[][] arr) {
		for (int i = 0; i < N; i++) {
			System.out.println(Arrays.toString(arr[i]));
		}
		System.out.println("------------------------------------");
	}

	static boolean check(int[][] arr) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j] == 0) {
					return false;
				}
			}
		}
		return true;
	}

	static int[][] deepcopy(int[][] arr) {
		int[][] copy = new int[arr.length][arr[0].length];
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				copy[i][j] = arr[i][j];
			}
		}
		return copy;
	}

}

---

결과

 

---