[백준] 17142. 연구소 3 (Java)

 

🔒 문제

17142번: 연구소 3

 

🔑 알고리즘

브루트포스, 조합론, 그래프 탐색, 너비우선탐색(BFS)

 

 

💡  풀이

전체 바이러스 중 M개의 바이러스를 선택하여 활성 바이러스로 표시한 후,

너비우선탐색(BFS)를 이용하여 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구했다.

 

입력을 받으며 각 바이러스들의 좌표를 리스트에 저장하고, 퍼뜨려야할 빈 칸의 수를 센다.

 

다음으로 전체 바이러스 중 M개의 바이러스를 고르는데, 이때 바이러스의 순서는 중요하지 않기 때문에 조합을 사용한다.

for (int i = start; i < virusList.size(); i++) {
	if (!selected[i]) {
		selected[i] = true;
		comb(count + 1, i + 1);
		selected[i] = false;
	}
}

 

M개의 바이러스를 골랐다면

활성 바이러스와 비활성 바이러스를 구분하기 위해 고른 바이러스의 값을 2에서 3으로 변경하고

해당 바이러스들의 좌표와 현재 시간에 해당하는 0을 큐에 삽입한다.

for (int i = 0; i < selected.length; i++) {
	if (selected[i]) {
		Virus virus = virusList.get(i);
		queue.add(new Virus(virus.y, virus.x, 0));
		board[virus.y][virus.x] = 3;
	}
}

 

이제 상하좌우 네 방향으로 탐색하며 BFS를 진행한다.

만약 탐색한 곳이 비활성 바이러스(2)인 경우

활성 바이러스에 해당하는 3으로 변경한 후 큐에 삽입하고

 

탐색한 곳이 빈 칸(0)이라면

활성 바이러스에 해당하는 3으로 변경한 후 큐에 삽입하고 바이러스를 퍼뜨린 칸을 세는 count 값을 1 증가시킨다.

이때 증가시킨 값이 처음에 셌던 빈 칸의 값과 동일하다면 모든 빈 칸에 바이러스를 퍼뜨린 것으로 최소 시간을 구한 것이다.

 

탐색한 곳이 벽 혹은 활성 바이러스(1, 3) 이라면 아무것도 하지 않아도 된다.

// 비활성 바이러스
if (board[ny][nx] == 2) {
	queue.add(new Virus(ny, nx, cur.t + 1));
	board[ny][nx] = 3;
}

// 빈칸
if (board[ny][nx] == 0) {
	queue.add(new Virus(ny, nx, cur.t + 1));
	board[ny][nx] = 3;

	if (++pollutionCount == blankCount) {
		min = Math.min(min, cur.t + 1);
		break label1;
	}
}

 

BFS를 진행하면서 현재 시간이 기록된 최소 시간을 넘었다면 유망하지 않기 때문에 더 이상 탐색하지 않는 백트래킹을 사용하여 시간을 단축시킬 수 있다.

if (cur.t > min)
	break;

 

 

* board 의 값에 바이러스를 기록하기 때문에 BFS 시작 전의 board 배열을 복사해두었다가 BFS가 끝나면 원상 복구해야한다.

 

 

✏️ 코드

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[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int N, M, board[][], min, blankCount;
	static ArrayList<Virus> virusList;
	static boolean[] selected;

	static public void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		init();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				int num = Integer.parseInt(st.nextToken());
				board[i][j] = num;

				// 빈 칸이라면 count 증가
				if (num == 0)
					blankCount++;
				
				// 바이러스라면 좌표 저장
				if (num == 2) {
					virusList.add(new Virus(i, j, 0));
				}
			}
		}
		selected = new boolean[virusList.size()];
		
		if (blankCount == 0) {
			System.out.println(0);
			return;
		}
		

		comb(0, 0);

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

	private static void init() {
		board = new int[N][N];
		virusList = new ArrayList<>();
		min = Integer.MAX_VALUE;
		blankCount = 0;
	}

	private static void comb(int count, int start) {

		if (count == M) {
			// 임시 배열 생성
			int[][] tmp = new int[N][N];
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					tmp[i][j] = board[i][j];

			// 바이러스 선택 및 표시
			Queue<Virus> queue = new LinkedList<>();
			for (int i = 0; i < selected.length; i++) {
				if (selected[i]) {
					Virus virus = virusList.get(i);
					queue.add(new Virus(virus.y, virus.x, 0));
					board[virus.y][virus.x] = 3;
				}
			}

			int pollutionCount = 0;
			label1: while (!queue.isEmpty()) {
				Virus cur = queue.poll();

				if (cur.t > min)
					break;

				for (int i = 0; i < dy.length; i++) {
					int ny = cur.y + dy[i];
					int nx = cur.x + dx[i];

					if (ny < 0 || ny >= N || nx < 0 || nx >= N)
						continue;

					// 비활성 바이러스
					if (board[ny][nx] == 2) {
						queue.add(new Virus(ny, nx, cur.t + 1));
						board[ny][nx] = 3;
					}

					// 빈칸
					if (board[ny][nx] == 0) {
						queue.add(new Virus(ny, nx, cur.t + 1));
						board[ny][nx] = 3;

						if (++pollutionCount == blankCount) {
							min = Math.min(min, cur.t + 1);
							break label1;
						}
					}
				}
			}

			// 원상 복구
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					board[i][j] = tmp[i][j];

			return;
		}

		for (int i = start; i < virusList.size(); i++) {
			if (!selected[i]) {
				selected[i] = true;
				comb(count + 1, i + 1);
				selected[i] = false;
			}
		}
	}

	static class Virus {
		int y, x, t;

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

	}
}