[백준_17142번] 연구소 3_삼성 SW 역량테스트

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보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

class virus {
	int x, y, time;
	
	public virus(int x, int y, int time) {
		this.x=x;
		this.y=y;
		this.time=time;
	}
}

public class BaekJoon_17142 {
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	static int[][] map;
	static ArrayList<virus> arr=new ArrayList<>(); // 초기 바이러스의 위치를 저장한 리스트
	static virus[] active;
	static int n,m,time=Integer.MAX_VALUE,originempty=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		map=new int[n][n];
		active=new virus[m];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				map[i][j]=sc.nextInt();
				
				if(map[i][j]==0) // 빈 공간 갯수 count
					originempty++; 
				else if(map[i][j]==2) // 바이러스 위치 저장(시간은 0으로 초기화)
					arr.add(new virus(i,j,0));
			}
		}
		
		// 안전지역의 갯수가 0개라면 종료
		if(originempty==0)
			System.out.println(0);
		else {
			dfs(0,0);
			// 소요시간이 갱신이 되지 않았다면 바이러스를 모든 칸에 퍼뜨릴수 없는 경우
			System.out.println(time==Integer.MAX_VALUE?-1:time);
		}
	}
	
	// 바이러스 전파 함수
	static void spreadvirus(int emptyspace) {
		Queue<virus> q=new LinkedList<>();
		boolean[][] visited=new boolean[n][n]; 
		
		// 활성화된 m개의 바이러스 방문처리&큐에 삽입
		for(int i=0;i<m;i++) {
			virus v=active[i];
			visited[v.x][v.y]=true;
			q.add(v);
		}
		
		while(!q.isEmpty()) {
			virus v=q.poll();
			
			// 상,하,좌,우 탐색
			for(int i=0;i<4;i++) {
				int nx=v.x+dx[i];
				int ny=v.y+dy[i];
				
				// 배열 범위를 넘어가거나 or 이미 전파가 된 칸이거나 or 벽인 경우는 넘어간다.
				if(nx<0||ny<0||nx>=n||ny>=n||visited[nx][ny]||map[nx][ny]==1) 
					continue;
				
				// 안전지역인 경우 안전지역의 갯수 감소
				if(map[nx][ny]==0)
					emptyspace--;
				
				// 안전지역의 갯수가 0이 된 경우는 소요시간 갱신
				if(emptyspace==0) {
					time=Math.min(time,v.time+1);
					return;
				}
				
				visited[nx][ny]=true; // 방문처리
				q.add(new virus(nx,ny,v.time+1)); // 소요시간을 늘려 큐에 삽입
			}
		}
	}
	
	// m개의 바이러스를 활성화 하는 함수
	static void dfs(int depth, int start) {
		// m개의 바이러스를 활성화 했다면 바이러스 전파
		if(depth==m) {
			spreadvirus(originempty);
			return;
		}
		
		// 연걸리스트에 있는 초기 바이러스 중 중복없이 m개 선택
		for(int i=start;i<arr.size();i++) {
			active[depth]=arr.get(i);
			dfs(depth+1,i+1);
		}
	}
}

 

[고찰]

 이번 문제는 이전에 풀었던 삼섬 SW 역량테스트 기출문제 중 연구소 문제의 상위 호환 문제였다. 초기 n개의 바이러스 중 m개의 바이러스를 활성화 하기 위해서는 DFS 알고리즘을 사용해야 하고, 활성화 된 m개의 바이러스를 기준으로 상, 하, 좌, 우에 바이러스를 퍼뜨리기 위해서는 BFS 알고리즘을 사용해야 한다. 

 

*** 0) 초기설정

 0-1) 바이러스가 퍼지면서 소요 시간도 저장해야 하기 때문에 바이러스의 위치와 시간을 저장하는 클래스를 사용한다.

 0-2) 맵의 정보를 입력받으면서 연결리스트에 초기 바이러스의 위치를 저장해두고 이후 m개의 바이러스를 선택할 때 사용한다.

 0-3) 해당 문제에서는 안전 지역의 개수가 0일때의 소요 시간을 구해야하기 때문에 초기 맵에서 안전 지역의 갯수를 count한다. 

 

*** 1) m개의 바이러스 활성화 하기

 1-1) 초기 바이러스의 위치를 저장한 연결리스트 중 중복 없이 m개의 바이러스를 선택하기 위해 DFS 알고리즘을 사용한다.

 1-2) 중복 없이 선택하기 위해 for 문의 시작 변수를 조정하는 매개변수를 사용하고, m개의 바이러스를 활성화 했다면 바이러스를 퍼뜨리는 함수를 실행한다.

 

*** 2) 바이러스 퍼뜨리기 

 2-1) 우선 활성화 한 m개의 바이러스를 방문처리 & 큐에 삽입한다.

 2-2) BFS 알고리즘을 사용하여 초기 바이러스의 위치를 기준으로 상, 하, 좌, 우 탐색을 시작한다.

 2-3) 탐색 위치가 배열 범위를 초과했거나, 이미 바이러스가 전파된 칸이거나, 벽이라면 넘어간다.

 2-4) 이외의 경우(탐색 위치가 안전 지역이거나 활성화가 되지 않은 바이러스가 있는 칸)라면 방문처리와 큐에 삽입 과정을 수행한다.

 

이번 문제는 문제에서 힌트를 주었듯이 각 칸에서의 전파 시간을 확인하는 것이 효율적이기 때문에 바이러스의 위치를 저장할 클래스를 선언할 때 전파 시간을 저장할 변수도 만드는 것이 중요했다. 또한 모든 과정이 끝났을 때 안전 영역의 개수가 0인지 확인해야 하는 부분에서 매번 for문을 돌려 전체 맵을 탐색하게 되면 시간초과가 나기 때문에 초기의 안전 영역의 개수에서 바이러스가 전파될 때 마다 전체에서 감소시켜 주는 것이 시간초과 없이 문제를 해결할 수 있는 방법이었다. 이때 주의해야 할 점은 다음 경우의 수를 위해 안전 영역의 개수가 저장된 전역변수를 사용하는 것이 아닌 매개변수로 전달된 변수를 사용해야 한다는 것이다.