백준 17142 <연구소 3>

이전에 풀었던 연구소 1 보다 어려워진 문제이다. 

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

14502번: 연구소

이 문제를 풀기 전에 위의 링크의 연구소를 풀지 않았다면 먼저 풀고 이 문제를 풀기를 바란다.

 

위 문제와 유사하게 바이러스의 개수는 최대 10개이기 때문에 M개가 주어지면 10 C M 조합을 이용하여 확산할 바이러스를 구하고 해당 바이러스를 Queue에 넣고 BFS를 해서 최소 시간을 구하는 문제이다.

 

이 문제를 풀면서 가장 중요하다고 느꼈던 건 예외사항을 잘 체크하고 결과가 만족하게 된다면 빠져나와야 하는 것이다.

 

즉 이 문제의 핵심은 빈칸의 유무를 판단하는 것과 빈칸이 없다면 종료하는 것! 

 

이런 문제를 많이 접근하다보니 깨달은 것은 ArrayLsit를 적극 활용하는 것이 좋다.

 

바이러스의 위치를 ArrayLsit에 담고 그것을 이용해 조합을 구하는것이 첫 번째 목표이다. 또한 처음에 입력할 때 빈칸의 개수를 세어서 조건을 체크해준다.

 

 time이라는 최종 결과 값을 -1로 초기화 하고 human이라는 빈칸의 개수를 세어주는 변수를 두어 예외사항을 처리해주었다.

 

그렇게 함으로써 빈칸의 갯수가 존재하지 않는다면 0을 결과로 두고 그렇지 않다면 조합을 구하는 것이다.

 

 

이 부분은 지금까지 계속 해왔던 조합을 구하는 문제이다.

 바이러스의 갯수가 총 10개이기 때문에 아무리 해도 1만이 넘지 않고 이를 이용해 BFS를 한다고 해도 칸의 크기가 총 2500 이기 때문에 총횟수가 2천500이 넘지 않아 문제를 간단하게 해결할 수 있다. 

 

GO라는 함수에는 선택된 바이러스를을 큐에 모두 담고 BFS를 실행하는 코드가 있다.

 

Queue에 선택된 바이러스를 담고 그지점을 visit처리를 해주었다.

 

그리고 count 변수를 두어 총 빈칸수와 같아지게 되면 현재 시간에 +1 한값과 time값을 비교해서 넣어주고 return을 하게 해 주었다.

 

전체 코드

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static class g {
		int x;
		int y;
		int t;

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

	static int map[][], n, m, visit[][], dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static int human, count, time = -1;
	static ArrayList<Point> virus = new ArrayList<Point>(), ghkf = new ArrayList<Point>();

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = kb.nextInt();
				if (map[i][j] == 0) {
					human++;
				} else if (map[i][j] == 2) {
					virus.add(new Point(i, j));
				}
			}
		}
		if(human!=0) 
			start(0);
		else {
			time=0;
		}
		System.out.println(time);
	}

	public static void start(int i) {//
		if (ghkf.size() == m) {
			go();
		}
		if (i == virus.size())
			return;
		ghkf.add(virus.get(i));
		start(i + 1);
		ghkf.remove(virus.get(i));
		start(i + 1);
	}

	public static void go() {
		visit = new int[n][n];
		count = 0;
		Queue<g> q = new LinkedList<g>();
		for (int i = 0; i < ghkf.size(); i++) {
			q.add(new g(ghkf.get(i).x, ghkf.get(i).y, 0));
			visit[ghkf.get(i).x][ghkf.get(i).y] = 1;
		}
		while (!q.isEmpty()) {
			g next = q.remove();

			for (int i = 0; i < 4; i++) {
				int x1 = next.x + dir[i][0];
				int y1 = next.y + dir[i][1];
				if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < n && map[x1][y1] != 1 && visit[x1][y1] == 0) {
					visit[x1][y1] = 1;
					q.add(new g(x1, y1, next.t + 1));
					if (map[x1][y1] == 0) {
						count++;
					}
					if (count == human) {
						if (time == -1) {
							time = next.t+1;
						} else
							time = Math.min(time, next.t+1);
						return;
					}
				}
			}
		}
	}

}