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

#17142 연구소 3

난이도 : 골드 4

유형 : 그래프 탐색/ BFS/ 순열 

17142번: 연구소 3

▸ 문제

▸ 입력

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

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

▸ 출력

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

 

 

문제 풀이 

중복 순열로 바이러스의 가능한 조합을 모두 만들어 BFS탐색을 돌려 최소 시간을 찾는 문제이다. 솔직히 이 문제는 골드4는 아니고 골드 2~3은 되는 문제인 것 같다. 

 

이제 차근차근 풀이를 해보자!

 

📚 조건

• 연구소의 크기 N ( 4 <= N <= 50)
• 바이러스의 개수 M ( 1 <= M <= 10) >  순열을 사용하기 때문에 다행히도 범위를 작게 주었다
• 0은 빈 칸, 1은 벽, 2는 바이러스

 

 

1) 처음으로 해야 될 것은 바이러스의 모든 순열을 맞춰 보는 것이다.

 

바이러스의 위치를 조합하기 위해서는 좌표가 아닌 숫자로 바꿔줬다. NxN 크기의 배열 (i,j)의 index  → i*N+j 

 

그리고 해당 문제는 순서 o, 중복 x 인 순열을 구하면 되므로 dfs 재귀를 사용하여 순서를 맞춰주면 된다. 뒤에 들어와있는 숫자를 빼주고 새로운 순열을 계속해서 조합해주기 위해 LIFO구조인 Stack을 사용했다. 

ex) arr : [ 1 2 3 4 ], virus_len :3

       1)  1 2 3  > 123

       2) 1 2 3 4  (LIFO)  >124

         ...

static void virusCombination(Stack<Integer> comb, int pos, int len) {
		if(pos > vList.size()) return ;
		
		if(len == m ) {
			for(int i : vComb) {
				System.out.print(i+" ");
			}
			System.out.println();
			return ;
		}
		
		for(int i=pos; i<vList.size(); i++) {
			comb.push(vList.get(i));
			virusCombination(comb, i+1, len+1);
			comb.pop();
		}
		return ;
	}

 

 

 

2) 이젠 바이러스의 여러 조합의 경우의 수를 가지고 BFS탐색을 해주면 된다. 그리고 그 중에서 가장 적은 시간을 내는 값을 골라 저장해주면 된다.

 

해당 BFS탐색은 시작이 여러 곳인 탐색이므로 turn이라는 개념을 도입해야 한다.

 

그냥 싸이클이라고 생각하면 된다. 한 턴을 주기로 시작점인 바이러스들이 동시에 움직이고 시간을 카운트해주면 된다.

그러기 위해서는 queue특성상 계속해서 while 반복문을 돌기 때문에 한 턴에 속해있는 queue.size()만큼만 돌려주면 된다. 탐색 종료 시점은 0인 공간이 없으면 종료한다. 0의 갯수는 입력받을 때 미리 해뒀다.

static int bfs(List<Integer> vComb) {
	Queue<int[]> q = new LinkedList<>();
	boolean[][] check = new boolean[n][n];
	for(int start : vComb) {
		int sx = start%n;
		int sy	= start/n;
		q.add(new int[] {sx,sy});
		check[sy][sx] = true;
	}
	
	int restCnt = space;
	int time =0;
	while(!q.isEmpty()) {
		
		int size = q.size();
		for(int turn=0; turn<size; turn++) {
			int[] pos = q.poll();
			int px = pos[0];
			int py = pos[1];
			
			for(int i=0; i<4; i++) {
				int nx = px + dx[i];
				int ny = py + dy[i];
				
				if(nx < 0 || ny < 0 || nx > n-1 || ny > n-1 || check[ny][nx]) continue;
               
				if(map[ny][nx] == 0 ) {  // || map[ny][nx] ==2 도 추가 해줘야 함
					check[ny][nx] = true;
					q.add(new int[] {nx,ny});
					if(map[ny][nx]==0) restCnt--;
				}
			}
		}
		
		// 한 싸이클 카운트 
		time ++;
		
		// 바이러스 모두 퍼졌으면 리턴 
		if(restCnt ==0) {
			return time;
		}
		
	}
	return -1;
	
}

 

 

 

아직 끝이 아니다! 예외처리가 남았다. 실무에서는 테스트케이스를 직접 만들어야 하기 때문에 꼼꼼히 해보자.

 

 

 

1) 0 or ALL

만약 0인 공간이 아예 없거나 아예 꽉찬 경우를 생각해보자. 아 그런데 조건을 보면 바이러스가 최소 1개이므로 ALL은 생각 안해도 된다.

그런데 0인 공간이 0일 때의 조건은 없으므로 예외처리를 해두자. 만약 하지않으면 싸이클은 무조건 1번은 돌기 때문에 1이 출력 될 것이다.

4 4
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1

answer = 0
예외처리 안 할 경우 = 1

if(space ==0) {
	System.out.println(0);
}else {
	Stack<Integer> vs = new Stack<>();
	virusCombination(vs, 0,0);
	System.out.println(result == Integer.MAX_VALUE? -1 : result);
}

 

2) 비활성화된 바이러스도 탐색이 가능한가?

 

예제 케이스만 보고 생각했기 때문에 이 부분을 간과하고 지나쳤었다. 활성화된 바이러스가 비활성화된 바이러스를 지나쳐서 움직일 수 있기 때문에 이 부분도 탐색의 조건에 넣어줘야한다.

11 2
1 1 0 1 1 1 1 1 0 1 1
1 1 2 1 1 1 1 1 2 1 1
0 1 2 1 1 1 0 1 2 1 1
0 1 0 1 1 1 0 1 0 1 1
0 0 2 0 0 1 0 0 2 0 0
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1

answer = 4
예외처리 안 할 경우 = -1 

if(map[ny][nx] == 0 || map[ny][nx] ==2) {
	check[ny][nx] = true;
	q.add(new int[] {nx,ny});
	if(map[ny][nx]==0) restCnt--;
}

 

풀이 코드 

최종코드는 다음과 같다. 한 가지 드는 생각은 이런 문제가 만약 테스트케이스가 주어지지 않은 상태에서 코딩하면 한 번에 100% 코드를 낼 수 있을까? 하는 생각이 들었다. 문제에 대한 집중력은 물론이거니와 설계에 대한 중요성이 다시금 느끼는 문제였다. 

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

public class Main {

	static int n,m, space, result = Integer.MAX_VALUE;
	static int[][] map;
	static List<Integer> vList;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static 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());
		
		map = new int[n][n];
		
		vList = new ArrayList<>();
		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());
				if(num==2) {
					vList.add(i*n+j);
				}else if(num==0) {
					space ++;
				}
				map[i][j]= num; 
				
			}
		}
		if(space ==0) {
			System.out.println(0);
		}else {
			Stack<Integer> vs = new Stack<>();
			virusCombination(vs, 0,0);
			System.out.println(result == Integer.MAX_VALUE? -1 : result);
		}
	}
	
	static void virusCombination(Stack<Integer> comb, int pos, int len) {
		if(pos > vList.size()) return ;
		
		if(len == m	) {
			List<Integer> vComb = new ArrayList<>();
			for(int num : comb) {
				vComb.add(num);
			}
			int takeTime = bfs(vComb);
			if(takeTime != -1) {
				result = Math.min(result, takeTime);
			}
			return ;
		}
		
		for(int i=pos; i<vList.size(); i++) {
			comb.push(vList.get(i));
			virusCombination(comb, i+1, len+1);
			comb.pop();
			
		}
		return ;
		
	}
	
	static int bfs(List<Integer> vComb) {
		Queue<int[]> q = new LinkedList<>();
		boolean[][] check = new boolean[n][n];
		for(int start : vComb) {
			int sx = start%n;
			int sy	= start/n;
			q.add(new int[] {sx,sy});
			check[sy][sx] = true;
		}
		
		int restCnt = space;
		int time =0;
		while(!q.isEmpty()) {
			
			int size = q.size();
			for(int turn=0; turn<size; turn++) {
				int[] pos = q.poll();
				int px = pos[0];
				int py = pos[1];
				
				for(int i=0; i<4; i++) {
					int nx = px + dx[i];
					int ny = py + dy[i];
					
					if(nx < 0 || ny < 0 || nx > n-1 || ny > n-1	|| check[ny][nx]) continue;
					
					if(map[ny][nx] == 0 || map[ny][nx] ==2) {
						check[ny][nx] = true;
						q.add(new int[] {nx,ny});
						if(map[ny][nx]==0) restCnt--;
						
					}
				}
			}
			
			// 한 싸이클 카운트 
			time ++;
			
			// 바이러스 모두 퍼졌으면 리턴 
			if(restCnt ==0) {
				return time;
			}
			
		}
		return -1;
		
	}
}