17142 연구소3 - 삼성 sw 역량 기출

연구소3

N * N 연구소에 바이러스를 유출한다.

모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 빈칸으로 복제되며 1초가 걸린다.

연구소는 빈 칸, 벽, 바이러스로 이루어져있다.

0 빈칸, 1 벽, 2 바이러스 위치이다.

활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

M 개의 바이러스를 활성화 시켰을 때 모든 빈칸이 바이러스가 될 수 있는 가장 짧은 시간은?

---

풀이

1. 바이러스 확산을 구현한다
   • bfs를 이용하여 빈칸이나 바이러스가 있는 곳으로만 상하좌우로 이동할 수 있도록 한다.
   • 시간을 계산하기 위해 새로운 N*N 배열에 시간을 누적해준다.
     • 큐에서 꺼낸 좌표 + 1
2. 활성화할 바이러스를 선택하는 모든 경우의 수를 찾는 메소드를 구현한다.
   • visit배열을 선언하여 선택하는 경우와 선택하지 않은 경우를 구현한다.
   • 선택을 M개만큼 했으면 계산을 해준다.
     • 기존 map에 영향이 없도록 copyMap을 생성해준다.
     • 누적 시간을 저장할 배열을 만들어준다. - result[][]
     • 큐에 선택한 좌표를 넣어준다.
     • bfs를 실행한다.
     • 빈 칸이 없는지 확인한다.
     • 빈 칸이 없다면 바이러스가아니고 벽이 아닌 곳 중 시간의 최대값을 구한다.
     • 전역변수에 최소값을 저장한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main연구소3{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());
		int[][] map = new int[N][N];
		virus= new ArrayList<int[]>();

		for(int i = 0; i < N; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st2.nextToken());
				if(map[i][j] == 2) {
					virus.add(new int[] {i,j});
				}
			}
		}


		ans = Integer.MAX_VALUE;
		inputVirus(0, 0, map, new int[virus.size()]);
		if(ans == Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(ans);			
		}

	}
	static int N;
	static int M;
	static int ans;
	static List<int[]> virus;
	static int[] dx = { 1, -1, 0 ,0};
	static int[] dy = { 0, 0, 1, -1};

	static void inputVirus(int idx, int cnt, int[][] map, int[] visit) {
		if(cnt == M) {
			int[][] result = new int[N][N];
			int[][] copy = new int[N][N];
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					result[i][j]=Integer.MAX_VALUE;
					copy[i][j]=map[i][j];
				}
			}

			Queue<int[]> queue = new LinkedList<>();
			for(int i = 0; i < visit.length; i++) {
				if(visit[i] == 1) {
					int[] q = virus.get(i);
					queue.add(q);
					result[q[0]][q[1]] = 0;
				}
			}


			bfs(copy, result, queue);

			int chk=0;
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(copy[i][j] == 0) {
						chk=1;
						break;
					}
				}
			}
			if(chk == 0) {
				int max = 0;
				for(int i = 0; i < N; i++) {
					for(int j = 0; j < N; j++) {
						if(result[i][j] != Integer.MAX_VALUE && map[i][j]!=2) {
							max = Math.max(max, result[i][j]);
						}
					}
				}
				ans = Math.min(max, ans);
				return;
			}else {
				return;
			}

		}
		if(idx == virus.size()) {
			return;
		}

		//선택함
		visit[idx] = 1;
		inputVirus(idx+1, cnt+1, map, visit);
		//선택안함
		visit[idx] = 0;
		inputVirus(idx+1, cnt, map, visit);

	}


	static void bfs(int[][] map, int[][] check, Queue<int[]> queue) {
		while(!queue.isEmpty()) {
			int[] q = queue.poll();
			map[q[0]][q[1]] = 3;


			for(int i = 0; i < 4; i++) {
				int yi = q[0] + dy[i];
				int xi = q[1] + dx[i];

				if(yi >= N || xi >= N || yi < 0 || xi < 0 || map[yi][xi] == 1)continue;

				if( check[yi][xi] > check[q[0]][q[1]]+1 ) {

					check[yi][xi] = check[q[0]][q[1]]+1;
					queue.add(new int[] {yi,xi});
				}
			}
		}
	}
}