[백준 / JAVA] 17142. 연구소 3 (G3)

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

 

요즘 큰 산 두개를 넘으니 자기개발을 통 안한다는 생각이 들었다. 그래서 목표 중 하나였던 백준 플레를 인생에서 가장 젊을 때 다시 도전해보려 한다.

 

무려 약 100일 만에 푸는 알고리즘이다. 그래서 코드를 전부 짜기보다 기존 코드를 참고하여 풀 수 있는 문제를 골랐다. 이 문제의 함정(?)은 비활성 바이러스도 바이러스로 칸을 채운 취급을 한다는 것이다. 사실 마지막 예제을 보면 쉽게 알 수 있지만 출제자가 그 예제를 맨 밑에 박아놓은 덕분에 나도 밑바닥을 보고 왔다. 

 

개발자놈들은 성격이 이상해, 성격이!

 

골3 하나에 4점 오르는데 언제 플레가지

 

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		numbers = new int[M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int input = Integer.parseInt(st.nextToken());
				map[i][j] = input;
				if (input == 0)
					zeroList.add(new Point(i, j));
				else if (input == 2)
					virusList.add(new Point(i, j));
			}
		}
		comb(0, 0);
		System.out.println(min);
	}

	static int N, M, map[][], numbers[], min = -1, dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };
	static ArrayList<Point> zeroList = new ArrayList<>(), virusList = new ArrayList<>(),
			activeVirusList = new ArrayList<>();

	static void bfs() {
		boolean visited[][] = new boolean[N][N];
		Deque<Point> q = new LinkedList<>();
		int time = 0;
		int emptySpace = zeroList.size(); // 채워야하는 빈칸 수
		for (Point v : activeVirusList) {
			q.add(v);
			visited[v.row][v.col] = true;
		}
		while (!q.isEmpty()) {
			if (emptySpace < 1) {
				if (min == -1)
					min = time;
				else
					min = Integer.min(min, time);
				return;
			}
			int size = q.size();
			time++;
			for (int t = 0; t < size; t++) {
				Point cur = q.poll();
				for (int d = 0; d < 4; d++) {
					int nr = cur.row + dr[d];
					int nc = cur.col + dc[d];
					if (nr < 0 || nc < 0 || nr >= N || nc >= N || map[nr][nc] == 1 || visited[nr][nc])
						continue;
					if (map[nr][nc] == 0)
						emptySpace--;
					q.add(new Point(nr, nc));
					visited[nr][nc] = true;
				}
			}
		}
	}

	static void comb(int count, int start) {
		if (count == M) {
			for (int n : numbers)
				activeVirusList.add(virusList.get(n)); // 활성 바이러스 리스트
			bfs();
			activeVirusList.clear();
			return;
		}
		for (int i = start; i < virusList.size(); i++) {
			numbers[count] = i;
			comb(count + 1, i + 1);
		}
	}

	static class Point {
		int row, col;

		public Point(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}
	}
}