[백준/자바] 17142 연구소 3

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을 출력한다.

예제 입력 1 

7 3
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

예제 출력 1 

4

예제 입력 2 

7 3
2 0 2 0 1 1 0
0 0 1 0 1 2 0
0 1 1 2 1 0 0
2 1 0 0 0 0 2
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2

예제 출력 2 

4

예제 입력 3 

7 4
2 0 2 0 1 1 0
0 0 1 0 1 2 0
0 1 1 2 1 0 0
2 1 0 0 0 0 2
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2

예제 출력 3 

4

예제 입력 4 

7 5
2 0 2 0 1 1 0
0 0 1 0 1 2 0
0 1 1 2 1 0 0
2 1 0 0 0 0 2
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2

예제 출력 4 

3

예제 입력 5 

7 3
2 0 2 0 1 1 0
0 0 1 0 1 0 0
0 1 1 1 1 0 0
2 1 0 0 0 0 2
1 0 0 0 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2

예제 출력 5 

7

예제 입력 6 

7 2
2 0 2 0 1 1 0
0 0 1 0 1 0 0
0 1 1 1 1 0 0
2 1 0 0 0 0 2
1 0 0 0 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2

예제 출력 6 

-1

예제 입력 7 

5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 1 1

예제 출력 7 

0

---

설명

조합 + bfs로 해결해야 하는 문제다.

문제를 꼼꼼히 읽지 않으면 틀리는데 이유는 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변하기 때문이다.

처음에는 비활성 바이러스를 벽처럼 변하지 않는 것으로 풀었는데 그렇게 풀면 안된다.

비활성 바이러스 역시 빈칸처럼 풀되 마지막 퍼트린 시간 계산시에는 계산에 포함하지 않아야 한다.

 

조합.

바이러스를 ArrayList로 받고 인덱스를 비트마스크 연산을 통해 m개 만큼 활성바이러스로 변할 것을 선택한다.

static void combination(int s) {
	for(int i = 0; i < (1 << s); i++) {
		if(Integer.bitCount(i) == m) {
			String digit = "%"+s+"s"; 
			String str = String.format(digit, Integer.toBinaryString(i)).replace(" ", "0");
			bfs(str);
		}
	}
}

 

bfs.

조합으로 선택된 인덱스를 활성 바이러스라고 생각하고 앞뒤좌우로 퍼져나간다.

이때 벽이 아닌 모든 공간(빈칸, 비활성 바이러스)로 퍼져나간다.

중요한 점은 벽이 아닌 모든 공간을 탐색했는지 여부이다.

이를 확인하기 위해 처음 벽이 아니고 활성 바이러스가 아닌 공간의 개수 = total이라고 한다.

bfs를 돌면서 len이라는 변수를 ++하면서 마지막에 len과 total의 개수가 다르면 탐색하지 않은 공간이 있다는 것으로 간주할 수 있다.

static void bfs(String s) {
		boolean v[][] = new boolean[n][n];
	    
        for(int i = 0; i < n; i++){
            System.arraycopy(visited[i], 0, v[i], 0, n);
        }
        
		int map[][] = new int[n][n];
		String str[] = s.split("");
		pq = new PriorityQueue<>();
		int max = 0;
		int len = 0;
		
		for(int i = 0; i < str.length; i++) {
			if(str[i].equals("1")) {
				pq.add(new coordinate(virus.get(i).x, virus.get(i).y, 0));
			}else map[virus.get(i).x][virus.get(i).y] = -1;
		}
		
		while(!pq.isEmpty()) {
			coordinate cur = pq.poll();
			if(v[cur.x][cur.y]) continue;
			if(map[cur.x][cur.y] != -1) max = Math.max(max, cur.count);
			if(cur.count != 0) len++;
			v[cur.x][cur.y] = true;
			
			for(int i = 0; i < 4; i++) {
				int tx = cur.x + dxy[i][0];
				int ty = cur.y + dxy[i][1];
				if(tx < 0 || n <= tx || ty < 0 || n <= ty) continue;
				if(v[tx][ty]) continue;
				pq.add(new coordinate(tx, ty, cur.count+1));
			}
		}
	if(len != total) return;
	min = Math.min(min, max);
		
}

코드