백준 17142 : 연구소 3

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

17142번: 연구소 3

[ 문제풀이 ]

바이러스를 선택할 수 있는 모든 경우의 수를 다해보면 해결할 수 있는 문제이다. 다만, 조심해야 할 점이 두 가지 있다.

​첫 번째는 마지막 예제처럼 바이러스를 퍼트릴 빈 공간(0)이 없다면 바이러스를 퍼뜨리지 말고 바로 종료해 줘야 한다.

​두 번째는 선택되지 않은 바이러스 영역이다. 선택되지 않은 바이러스(2)를 활성화시켜 다른 빈 공간(0)으로 퍼뜨릴 수 있다면 활성화시키고, 만약 선택되지 않은 바이러스(2)가 다른 빈 공간(0)으로 바이러스를 퍼트리지 않는다면 활성화시킬 필요가 없다. 나는 이를 구분하기 위해 cnt라는 변수를 사용해서 구분하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M, answer;
	static int[][] map;
	static boolean[][] visit;
	static List<Virus> list, viruses;
	static Queue<Virus> q;

	static int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

	static class Virus {
		int y, x, time, cnt;

		public Virus(int y, int x, int time, int cnt) {
			this.y = y;
			this.x = x;
			this.time = time;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		answer = Integer.MAX_VALUE;

		map = new int[N][N];
		list = new ArrayList<>();
		viruses = new ArrayList<>();
		q = new LinkedList<>();
		boolean flag = false;

		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0) flag = true;
				if (map[i][j] == 2) list.add(new Virus(i, j, 0, 0));
			}
		}

		visit = new boolean[N][N];

		//바이러스를 퍼뜨릴 빈 공간(0)이 없으면
		if (!flag) bw.write("0\n");
		//바이러스를 퍼뜨릴 빈 공간(0)이 있으면
		else {
			selectTheVirus(0, 0);
			bw.write((answer == Integer.MAX_VALUE ? -1 : answer) + "\n");
		}
		bw.flush();bw.close();br.close();
	}

	//모든 바이러스에서 M개를 선택하는 조합 함수
	public static void selectTheVirus(int depth, int cnt) {
		if (cnt == M) {
			spreadTheVirus();
			return;
		}

		for (int i = depth; i < list.size(); ++i) {
			viruses.add(list.get(i));
			selectTheVirus(i + 1, cnt + 1);
			viruses.remove(viruses.size() - 1);
		}
	}

	public static void spreadTheVirus() {
		for (int i = 0; i < N; ++i) Arrays.fill(visit[i], false);
		for (Virus v : viruses) {
			visit[v.y][v.x] = true;
			q.offer(v);
		}

		int time = 0;
		while (!q.isEmpty()) {
			Virus v = q.poll();

			//빈 공간(0)에 바이러스 퍼뜨린 경우 시간 업데이트
			if (v.cnt == 0 || v.cnt > 1) time = v.time;

			for (int d = 0; d < 4; ++d) {
				int ny = v.y + dir[d][0];
				int nx = v.x + dir[d][1];

				if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
				if (map[ny][nx] == 1 || visit[ny][nx]) continue;

				visit[ny][nx] = true;

				//현재 바이러스가 선택된 바이러스에 의해 감염된 경우
				if (v.cnt == 0) {
					if (map[ny][nx] == 2) q.offer(new Virus(ny, nx, v.time + 1, 1));
					else q.offer(new Virus(ny, nx, v.time + 1, 0));
				} 
				//현재 바이러스가 선택되지 않은 바이러스에 의해 감염된 경우
				else {
					if (map[ny][nx] == 2) q.offer(new Virus(ny, nx, v.time + 1, v.cnt));
					else q.offer(new Virus(ny, nx, v.time + 1, v.cnt + 1));
				}
			}
		}

		if (isVaild()) answer = Math.min(answer, time);
	}

	//벽을 제외한 모든 영역에 바이러스를 퍼뜨렸는지 확인
	public static boolean isVaild() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (map[i][j] == 1) continue;
				if (!visit[i][j]) return false;
			}
		}
		return true;
	}
}