[Java] BOJ17141, 백준 - 연구소2

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

17141번: 연구소 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512MB	5288	2411	1652	44.685%

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×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 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 5

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

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
5 - 3 2 3 4 5

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

 

입력

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

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

 

출력

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

 

<풀이>

* 시간복잡도 계산

바이러스 놓는 곳의 총 경우의 수: 놓을 수 있는 바이러스는 10개까지이니, 10개로 만들 수 있는 조합의 개수가 총 경우의 수일 것이다. 10Cn중 10C5일때 가장 수가 크니, 최대 경우의 수는 252가지

연구소 최대 크기가 50^2이고, 각각 바이러스를 놓는 경우마다 모든 칸을 방문해봐야하니,

O(N) = 252*50*50 = 630000

 

 

(1) 바이러스 놓는 칸 찾기

Point[] virus 배열을 만들어놓고, 입력이 들어올 때 2인 칸(바이러스 가능 칸)의 정보를 저장해놓는다.

최대 10개까지 나올 수 있으니, 초기 사이즈는 10

이 배열을 바탕으로 m과 재귀를 통해서 바이러스 놓는 칸의 모든 경우의 수를 찾는다.

private static void selectV(int cnt, int idx) {
	// '2'인 칸 중에 어떤 지점에 바이러스를 놓을지 결정
	if (cnt >= m) {
		// 모든 칸을 골랐다면 해당 칸으로 bfs를 수행하면 된다.
		bfs();
		return;
	}

	if (idx >= idxV)
		return;

	check[idx] = true;
	selectV(cnt + 1, idx + 1);
	check[idx] = false;
	selectV(cnt, idx + 1);
}

 

(2) 바이러스가 퍼지는 시간

이 부분이 어렵다면 이 문제를 먼저 풀고오는것을 추천!!!!!!!!!!!

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

7576번: 토마토

 

여러 개의 칸에서 시작하는 바이러스들이 퍼지는 최소 시간을 구해야하기때문에, 반드시 bfs를 써야함

bfs를 수행하기 위한 큐를 선언하고 초기 바이러스 위치를 큐에 담은 뒤,

for (int i = 0; i < 10; i++) {
	if (check[i]) {
		Point p = virus[i];
		q.add(p);
		visited[p.i][p.j] = true;
	}
}

 

BFS를 수행하면 된다.

while (!q.isEmpty()) {
	int size = q.size();
	for (int i = 0; i < size; i++) {
		Point p = q.poll();
		// 해당 점으로 바이러스를 퍼트려나간다.
		for (int j = 0; j < 4; j++) {
			int ni = p.i + move[j][0];
			int nj = p.j + move[j][1];

			// 인덱스 초과 또는 빈칸 아닌경우 또는 이미 방문한곳
			if (ni < 0 || nj < 0 || ni >= n || nj >= n || map[ni][nj] == 1 || visited[ni][nj])
				continue;

			// 빈칸인 경우 바이러스를 퍼뜨린다.
			visited[ni][nj] = true;
			q.add(new Point(ni, nj));
			currV++;
		}
	}
	time++;
}

 

BFS, 재귀, 사방 탐색을 모두 써야하는 정말 귀찮은 문제였다 ㅠㅠㅠ

 

<소스코드>

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

public class Main {

	private static int n, m, empty, min, idxV;
	private static int[][] map;
	private static boolean[] check;
	private static Point[] virus;
	private static boolean[][] visited;
	private static Queue<Point> q;
	private static boolean flag = false;

	private static int[][] move = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

	public static void main(String[] args) 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());
		empty = n * n;
		min = Integer.MAX_VALUE;

		virus = new Point[10];
		check = new boolean[10];
		idxV = 0;
		map = new int[n][n];
		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] == 1) {
					empty--;
				}
				if (map[i][j] == 2)
					virus[idxV++] = new Point(i, j);
			}
		} // end Input

		q = new LinkedList<>();

		selectV(0, 0);

		if (flag)
			System.out.println(min);
		else
			System.out.println("-1");
	}

	private static void bfs() {
		visited = new boolean[n][n];

		// 골라진 칸들을 큐에 다 넣는다.
		for (int i = 0; i < 10; i++) {
			if (check[i]) {
				Point p = virus[i];
				q.add(p);
				visited[p.i][p.j] = true;
			}
		}
		int time = -1;
		int currV = m;

		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Point p = q.poll();
				// 해당 점으로 바이러스를 퍼트려나간다.
				for (int j = 0; j < 4; j++) {
					int ni = p.i + move[j][0];
					int nj = p.j + move[j][1];

					// 인덱스 초과 또는 빈칸 아닌경우 또는 이미 방문한곳
					if (ni < 0 || nj < 0 || ni >= n || nj >= n || map[ni][nj] == 1 || visited[ni][nj])
						continue;

					// 빈칸인 경우 바이러스를 퍼뜨린다.
					visited[ni][nj] = true;
					q.add(new Point(ni, nj));
					currV++;
				}
			}
			time++;
		}

		// 다 끝났는데 바이러스가 다 채워짐
		if (currV == empty) {
			flag = true;
			min = Math.min(min, time);
		}

	}

	private static void selectV(int cnt, int idx) {
		// '2'인 칸 중에 어떤 지점에 바이러스를 놓을지 결정
		if (cnt >= m) {
			// 모든 칸을 골랐다면 해당 칸으로 bfs를 수행하면 된다.
			bfs();
			return;
		}

		if (idx >= idxV)
			return;

		check[idx] = true;
		selectV(cnt + 1, idx + 1);
		check[idx] = false;
		selectV(cnt, idx + 1);
	}
}

class Point {
	int i, j;

	Point(int i, int j) {
		this.i = i;
		this.j = j;
	}
}