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

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

17142번: 연구소 3

 

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

---

 

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

---

 

출력

연구소의 모든 빈 칸에빈칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

---

 

🚀풀이

조합, BFS 탐색을 알아야 하는 문제!

조합을 사용하여 전체 바이러스 중 M개만큼 바이러스 뽑아 활성화시킨 후 BFS를 사용하여 전체 맵을 탐색하는 시간 중 최소 시간을 구하면 되는 문제다.

주의해야 할 점이 맵에 있는 비활성화된 바이러스는 활성 바이러스와 만나면 활성화가 되지만, 바이러스를 퍼뜨리는 시간에는 포함되지 않는다는 점이 중요하다.

바이러스를 퍼뜨리는 시간을 기록하기 위해 이전 위치의 값 + 1을 다음 위치에 기록하면서 BFS 탐색을 진행하였다.

기록한 값이 0부터 시작되므로, 벽과 바이러스는 -1, -2로 바꿔서 map을 초기화했다.

바이러스가 모두 퍼지지 못한 경우를 체크하기 위해 사전에 빈칸(0)의 개수를 기록해 놓고, BFS 탐색 시 빈칸(0)에 방문했을 때 count를 증가시켜 전체 빈칸(0)의 개수와 비교하여 다르다면 모두 퍼지지 못한 경우라 판단하였다.

---

 

코드

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

public class Main {
	// 연구소 크기, 바이러스 개수, 최소시간, 연구소 빈칸(0)의 갯수
	static int N, M, min, zeroCount;
	// 연구소 맵, 연구소 맵 복사
	static int[][] map, map_copy;
	// 상, 우, 하, 좌 탐색
	static int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };
	// 바이러스 리스트
	static List<Point> virus;
	// 조합에서 M개만큼 뽑아내어 담아낼 배열
	static Point[] output;

	public static void main(String[] args) throws Exception {
		// 초기화
		init();
		// 문제 풀이
		solution();
		// 결과 출력
		printResult();
	}

	static void solution() {
		// 바이러스 갯수에서 M개 만큼 조합 생성
		combi(0, 0, virus.size(), M);
	}

	// 조합 함수
	static void combi(int start, int depth, int n, int r) {
		if (depth == r) {
			// 조합이 생성되면 바이러스 bfs 탐색
			bfs();
			return;
		}
		for (int i = start; i < n; i++) {
			output[depth] = virus.get(i);
			combi(i + 1, depth + 1, n, r);
		}
	}

	// bfs 함수
	static void bfs() {
		// 이번 bfs에서 사용할 map 복사
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map_copy[i][j] = map[i][j];
			}
		}

		Queue<Point> q = new LinkedList<>();	// 바이러스 큐 생성
		boolean[][] visited = new boolean[N][N];	// 방문 배열

		// 조합에서 M개 뽑아낸 바이러스를 큐에 삽입, map에는 0으로 기록
		for (int i = 0; i < M; i++) {
			q.offer(output[i]);
			map_copy[output[i].x][output[i].y] = 0;
			visited[output[i].x][output[i].y] = true;
		}

		int count = 0;	// 빈칸(0)에 몇번 방문했는지 체크
		while (!q.isEmpty()) {
			Point cur = q.poll();
			// 상, 우, 하, 좌 탐색
			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				// 범위 나가면 탐색 X
				if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
					continue;
				}
				// 이미 방문했으면 탐색 X
				if (visited[nx][ny]) {
					continue;
				}
				// 벽이면 탐색 X
				if (map_copy[nx][ny] == -1) {
					continue;
				}
				// 빈 칸(0)이면 count 증가
				if (map_copy[nx][ny] != -2) {
					count++;
				}
				map_copy[nx][ny] = map_copy[cur.x][cur.y] + 1; // 이전위치에서 +1 한 값을 map에 기록
				visited[nx][ny] = true;	// 방문처리
				q.offer(new Point(nx, ny));	// 큐에 삽입
			}
		}

		// 이번 탐색에서 빈칸에 바이러스를 모두 퍼뜨릴수 없을 경우 return
		if (count != zeroCount) {
			return;
		}

		// map에서 방문 시간을 체크하기 전, 비활성화된 바이러스들은 방문 시간에 포함되지 않으므로 0으로 초기화
		for (int i = 0; i < virus.size(); i++) {
			map_copy[virus.get(i).x][virus.get(i).y] = 0;
		}

		// map에서 최대 시간 찾기
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (max < map_copy[i][j]) {
					max = map_copy[i][j];
				}
			}
		}

		// 이번 최대 시간이 전체 시간 중 최소인지 비교
		if (max < min) {
			min = max;
		}
	}

	// 결과 출력
	static void printResult() {
		// min이 초기화값 그대로라면 바이러스 못퍼뜨린 경우이므로 -1 출력
		if (min == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(min);
		}
	}

	// 초기화
	static void init() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 연구소 크기
		M = Integer.parseInt(st.nextToken()); // 놓을 수 있는 바이러스 개수
		map = new int[N][N]; // 연구소 맵
		map_copy = new int[N][N]; // 연구소 맵 복사
		output = new Point[M]; // 바이러스들 중 M개만큼 조합에서 뽑아내 담을 매열
		min = Integer.MAX_VALUE; // 최소 시간 초기화
		virus = new ArrayList<>(); // 바이러스 리스트
		zeroCount = 0; // 연구소 맵 빈칸(0) 초기화
		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] == 2) {
					// 현재 바이러스라면 바이러스 리스트에 추가 및 map에는 -2로 기록
					virus.add(new Point(i, j));
					map[i][j] = -2;
				} else if (map[i][j] == 1) {
					// 현재 벽이라면 map 에 -1로 기록
					map[i][j] = -1;
				} else {
					// 빈 칸 갯수 기록
					zeroCount++;
				}
			}
		}
	}

	// 큐에 바이러스 위치를 넣을때 사용할 Point 클래스
	static class Point {
		int x, y;

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

 

결과