[17142] 연구소 3
얼마 전에 있었던 삼성SW역량테스트 문제입니다. 연구소 2 (https://daily-life-of-bsh.tistory.com/67) 문제와 브루트포스와 순열을 사용하여 BFS한다는 점은 같습니다. 다른점은 연구소 2 는 선택된 바이러스를 그냥 퍼뜨려서 바이러스가 꽉찬 시간의 최솟값을 구하면 되는 것이지만, 연구소 3 문제는 활성 바이러스가 비활성 바이러스 가 있는 칸으로 가면 비활성 바이러스가 활성 바이러스로 변한다는 점입니다.
그래서 연구소 2 문제는 선택된 바이러스만 2로 하고 나머지 바이러스는 0으로 바꿔서 최솟값을 구했지만, 연구소 3문제는 바이러스 2를 그대로 두면서 선택된 바이러스만 퍼뜨리면서 비활성 바이러스가 있는 자리도 바이러스가 있다고 보고 문제를 풀어야 했습니다. 예를 들어 연구소 3 에서 N=5, M=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 |
비활성 바이러스 중 하나를 골라서 활성 바이러스로 만들고 퍼뜨리는데 나머지가 모두 비활성 바이러스로 꽉차 있기 때문에 시간이 0초 걸립니다. 연구소 2에서 똑같은 예제를 넣고 했으면 (2,0) 바이러스가 선택 되었을 때 바이러스가 꽉차는 시간인 4초가 최솟값으로 선택 될 것입니다.
그래서 저는 먼저 바이러스 2가 있는 자리에 모두 visited를 true 로 체크해서 뽑힌 바이러스에서 BFS를 시행했는데, 그렇게 하게 되면 N=4, M=2 인 다음 예제에서 왼쪽과 오른쪽에서 바이러스를 1개씩 골랐을 때 최솟값 2초가 나와야 하는데, 이미 2가 visited가 true라고 체크 되어있기 때문에 바이러스를 퍼뜨리지 못하여 -1이 출력 되었습니다.
| 0 | 1 | 1 | 0 |
| 2 | 1 | 1 | 2 |
| 2 | 1 | 1 | 2 |
| 0 | 1 | 1 | 0 |
며칠 동안 생각날 때마다 문제를 켜서 생각해 본 결과, isFull() 이라는 함수를 새로 선언해서 문제를 해결했습니다. isFull()은 map에서 1과 2를 제외한 즉, 0인 좌표를 모두 검사해서 하나라도 visited가 false인 구역이 있으면 false를 반환하고 visited가 모두 true이면 true를 반환하는 함수 입니다.
처음부터 바이러스가 있는 자리에 visited 를 true라고 체크하는 것이 아닌, BFS를 시행하면서 시간을 1초 증가 시킬 때 isFull() 을 시행해서 map 에 바이러스가 모두 퍼져있는지 검사하면 되는 것이었습니다.
< 문제 풀이 >
list 에 뽑힌 순열을 저장하는데 까지의 과정은 연구소 2와 동일하기 때문에 생략하겠습니다. 순열이 뽑힐 때 부터 설명하겠습니다.
1. 뽑힌 바이러스의 순열을 queue에 하나씩 넣고, isFull()을 검사합니다. 만약에 true이면 map에 바이러스가 모두 퍼져있는 것이기 때문에, BFS를 실행할 필요가 없습니다. 그래서 초기 minute 값인 0을 result에 넣습니다.
2. 만약에 isFull() 이 false라면 바이러스가 퍼져있는 것이 아니기 때문에 BFS를 합니다.
3. BFS를 하는데 중요한 점은 queue의 size만큼 상하좌우로 탐색이 끝났다면, minute 을 1초 증가시키고 isFull()을 다시 검사한다는 점입니다. 이 점이 연구소 2와 다른 점입니다. 시간을 증가시키고 isFull() 을 검사하여서 바이러스가 이미 다 퍼진상태이면 더이상 BFS를 할 필요가 없기 때문에 BFS를 마무리 하기 위해서 return을 합니다.
4. 그렇게 해서 ArrayList 인 result에 있는 값중 최솟값을 출력하면 정답이 나오게 됩니다.
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
// 17142 연구소 3
public class Main {
static int N, M, minute;
static int [][] arr, map;
static ArrayList<Pair> virus, list, check;
static int [][] dir = {{1, 0},{0,1},{-1,0},{0,-1}};
static boolean [][] visited;
static ArrayList<Integer> result = new ArrayList<Integer>();
static Queue<Pair> queue;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
arr = new int[N][N];
virus = new ArrayList<Pair>();
list = new ArrayList<Pair>();
check = new ArrayList<Pair>();
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
arr[i][j] = sc.nextInt();
if(arr[i][j] == 2) {
virus.add(new Pair(i,j));
check.add(new Pair(i,j));
}
}
}
for(int i=0; i<virus.size(); i++) {
list.add(new Pair(0,0));
}
recur(0, 0);
if(result.isEmpty()) System.out.println("-1");
else {
int min = 987987987;
for(int i=0; i<result.size(); i++) {
min = Math.min(result.get(i), min);
}
System.out.println(min);
}
}
public static void recur(int start, int depth) {
if(depth == M) {
queue = new LinkedList<Pair>();
map = new int[N][N];
minute = 0;
visited = new boolean[N][N];
copy();
// queue 에 뽑힌 순열 넣기.
for(int i=0; i<M; i++) {
queue.add(list.get(i));
}
if(!isFull()) {
BFS();
}
// BFS 를 하고 나서 바이러스가 꽉찼다면
if(isFull()) result.add(minute);
return;
}
for(int i=start; i<virus.size(); i++) {
list.set(depth, virus.get(i));
recur(i+1, depth+1);
}
}
public static void BFS() {
while(!queue.isEmpty()) {
int len = queue.size();
for(int i=0; i<len; i++) {
Pair p = queue.poll();
visited[p.x][p.y]= true;
for(int j=0; j<4; j++) {
int nx = p.x+dir[j][0];
int ny = p.y+dir[j][1];
if(!isInside(nx, ny)) continue;
if(map[nx][ny] != 1 && visited[nx][ny] == false) {
queue.offer(new Pair(nx, ny));
visited[nx][ny] = true;
}
}
}
minute++;
if(isFull()) return;
}
}
// map 에 바이러스와 벽이 아닌 곳에 바이러스가 모두 퍼져있는지 검사하는 함수
public static boolean isFull() {
boolean flag = true;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(map[i][j] != 2 && map[i][j] != 1 && visited[i][j] == false) {
flag = false;
return flag;
}
}
}
return flag;
}
public static boolean isInside(int x, int y) {
if(x>=0 && x<N && y>=0 && y<N) return true;
else return false;
}
public static void copy() {
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
map[i][j] = arr[i][j];
}
}
}
}
class Pair {
int x, y;
Pair(int x, int y){
this.x=x;
this.y=y;
}
}