[BaekJoon] 17142 연구소 3 (Java)

1.  문제 링크

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

2.  문제

요약

• 바이러스는 활성 상태와 비활성 상태가 있고, 가장 처음에 모든 바이러스는 비활성 상태이며, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 이는 1초가 걸립니다.
• 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 합니다.
• 연구소는 크기가 N x N인 정사각형으로 나타낼 수 있으며, 정사각형은 1 x 1 크기의 정사각형으로 나누어져 있습니다.
• 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지합니다.
• 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변합니다.
• 연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제입니다.
• 입력: 첫 번째 줄에 4보다 크거나 같고 50보다 작거나 같은 연구소의 크기 N과 1보다 크거나 같고 10보다 작거나 같은 바이러스의 개수 M이 주어지고 두 번째 줄부터 N개의 줄에 연구소의 상태가 주어집니다.
  • 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치입니다.
  • 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수입니다.
• 출력: 첫 번째 줄에 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력합니다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, emptyNum, minTime = Integer.MAX_VALUE;
	static int[][] map;
	static ArrayList<Point> viruses;
	static LinkedList<Point> active;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		emptyNum = 0;
		map = new int[N][N];
		viruses = new ArrayList<>();
		active = new LinkedList<>();
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) {
				map[row][col] = scanner.nextInt();
				if(map[row][col] == 0) emptyNum++;
				else if(map[row][col] == 2) viruses.add(new Point(row, col, 0));
			}
		}
	}
	
	static void solution() {
		if(emptyNum == 0) {
			System.out.println(0);
			return;
		}
		findMinTime(0, 0);
		System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);
	}
	
	static void findMinTime(int idx, int depth) {
		if(depth == M) {
			int[][] copy = new int[N][N];
			for(int row = 0; row < N; row++) {
				for(int col = 0; col < N; col++) copy[row][col] = map[row][col];
			}
			bfs(copy);
			return;
		}
		for(int index = idx; index < viruses.size(); index++) {
			Point cur = viruses.get(index);
			active.add(cur);
			findMinTime(index + 1, depth + 1);
			active.remove(active.size() - 1);
		}
	}
	
	static void bfs(int[][] copy) {
		Queue<Point> queue = new LinkedList<Point>();
		boolean[][] visited = new boolean[N][N];
		for(Point p : active) {
			copy[p.x][p.y] = 3; 
			queue.offer(p);
		}
		int num = emptyNum;
		int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
		while(!queue.isEmpty()) {
			Point cur = queue.poll();
			for(int dir = 0; dir < 4; dir++) {
				int cx = cur.x + dx[dir], cy = cur.y + dy[dir];
				if(cx >= 0 && cx < N && cy >= 0 && cy < N && !visited[cx][cy]) {
					if(copy[cx][cy] == 0) num--;
					if(copy[cx][cy] == 0 || copy[cx][cy] == 2) {
						visited[cx][cy] = true;
						copy[cx][cy] = 3;
						queue.offer(new Point(cx, cy, cur.time + 1));
					}
				}
			}
			if(num == 0) {
				minTime = Math.min(minTime, cur.time + 1);
				return;
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Point {
		int x, y, time;
		public Point(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}