[CodeTree] 삼성 SW 역량테스트 2019 상반기 오후 2번 문제 - 바이러스 백신

문제 설명

N×N 크기의 도시에 병원과 벽을 제외한 모든 지역에 바이러스가 생겼습니다. 비용상의 문제로 모든 병원에서 백신을 공급할 수는 없어, M개의 병원을 적절히 골라 최대한 빨리 바이러스를 없애려고 합니다.

M개의 병원을 고르게 되면, 골라진 병원들을 시작으로 매 초마다 상하좌우로 인접한 지역 중 벽을 제외한 지역에 백신이 공급되기 때문에 그 자리에 있던 바이러스는 사라지게 됩니다.

예를 들어 위의 예에서 M=3 일때 다음과 같이 병원을 고른 경우를 생각해봅시다.

1초 뒤 모습은 다음과 같습니다.

각 위치마다 바이러스가 사라지는 데 걸리는 시간을 적어보면 다음과 같습니다.

따라서 위의 예에서는 모든 바이러스가 사라지는 데 총 5초의 시간이 걸립니다.

하지만 만약 처음 주어진 예에서 다음과 같이 병원들을 골랐다면, 3초만에 모든 바이러스를 없앨 수 있게 됩니다.

이런 상황에서 M개의 병원을 적절히 골라 바이러스를 전부 없애는데 걸리는 시간 중 최소 시간을 구하는 프로그램을 작성해보세요.

 

입력 형식

첫째 줄에는 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄 부터는 N개의 줄에 걸쳐 각 행의 상태에 해당하는 N개의 숫자가 공백을 사이에 두고 주어집니다. 숫자는 0,1,2 중에 하나이며, 0은 바이러스, 1은 벽 그리고 2는 병원이 있음을 의미합니다. 입력으로 주어지는 총 병원의 수가 항상 M보다 크거나 같고, 10을 넘지 않습니다.

• 3≤N≤50
• 1≤M≤10

출력 형식

M개의 병원을 적절히 골라 모든 바이러스를 없애는 데 필요한 최소 시간을 출력합니다. 만약 모든 바이러스를 없앨 수 있는 방법이 없다면 −1을 출력합니다.

 

입출력 예제

예제1

6 3
2 1 2 0 1 1
0 0 0 1 0 1
1 1 0 0 2 0
1 0 0 1 0 1
1 0 0 0 0 1
1 1 2 1 0 1

출력

>> 3

 

예제2

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

출력

>> -1

 

예제3

3 1
1 1 2
2 1 2
1 1 1

출력

>> 0

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, min = Integer.MAX_VALUE, total;
	static int[][] arr, dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	static ArrayList<Hospital> hospitals;
	static int[] pick;

	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());
		arr = new int[N][N];
		pick = new int[M];
		hospitals = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == 2) {
					hospitals.add(new Hospital(i, j));
				}else if(arr[i][j] == 0) {
					total++;
				}
			}
		}
		if(total == 0) {
			System.out.println(0);
			System.exit(0);
		}
		comb(0, 0);
		
		System.out.println(min == Integer.MAX_VALUE ? -1 : min);
	}

	private static void comb(int idx, int cnt) {
		if (cnt == M) {
			min = Math.min(min, bfs(total));
			return;
		}
		for (int i = idx; i < hospitals.size(); i++) {
			pick[cnt] = i;
			comb(i + 1, cnt + 1);
		}
	}

	private static int bfs(int total) {
		boolean[][] visit = new boolean[N][N];
		PriorityQueue<Hospital> q = new PriorityQueue<>((a, b)->a.time-b.time);
		for (int i = 0; i < M; i++) {
			Hospital now = hospitals.get(pick[i]);
			q.add(new Hospital(now.x, now.y, 0));
			visit[now.x][now.y] = true;
		}
		while (!q.isEmpty()) {
			Hospital now = q.poll();
			int x = now.x;
			int y = now.y;
			int time = now.time;
			for (int d = 0; d < 4; d++) {
				int nx = x + dir[d][0];
				int ny = y + dir[d][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] || arr[nx][ny] == 1)
					continue;
				if (arr[nx][ny] == 0) {
					total--;
				}
				if(total == 0) {
					return time+1;
				}
				visit[nx][ny] = true;
				q.add(new Hospital(nx, ny, time+1));
			}
		}
		return Integer.MAX_VALUE;
	}

	static class Hospital {
		int x, y, time;

		public Hospital(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		public Hospital(int x, int y, int time) {
			super();
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
}

 

[출처]

https://www.codetree.ai/training-field/frequent-problems/problems/vaccine-for-virus/description?page=2&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석