[코드트리] 바이러스 백신 - unsolved

       문제 요약        

- 문제

https://www.codetree.ai/frequent-problems/problems/vaccine-for-virus/description

 

 

 

         아이디어        

bfs 어디서 시작할지 

다음 방문할 위치는 WALL 이 아니기만 하면 된다 

조합 >> 중복되는 값  줄이기 

 

         소스코드        

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

public class Main {
	static int VIRUS = 0, WALL = 1, HOSPITAL = 2;
	static int N, M;

	static int[][] box;

	static int[] vacchine;
	static List<int[]> hospitals;

	static int[][] way = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	static int minTime;
	static int virus;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		hospitals = new ArrayList<>();

		box = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if (box[i][j] == HOSPITAL) {
					hospitals.add(new int[] { i, j });
				} else if (box[i][j] == VIRUS) {
					virus += 1;
				}
			}
		}

		if (virus == 0) {
			System.out.println(0);
			return;
		}

		vacchine = new int[M];
		minTime = Integer.MAX_VALUE;
		selectHospitals(0, 0);

		System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);
	}

	static void selectHospitals(int cnt, int idx) {
		if (cnt == M) {
			int minDestroyTime = simulate();
			if (minDestroyTime != -1) {
				minTime = Math.min(minTime, minDestroyTime);
			}
			return;
		}
		for (int i = idx; i < hospitals.size(); i++) { // idx부터 시작하여 중복 방지
			vacchine[cnt] = i;
			selectHospitals(cnt + 1, i + 1); // 다음 병원 선택 시 i + 1부터 시작
		}
	}

	static int simulate() {
		Queue<int[]> queue = new ArrayDeque<>();
		int[][] depth = new int[N][N];
		boolean[][] visited = new boolean[N][N];

		for (int id : vacchine) {
			int[] pos = hospitals.get(id);
			queue.add(new int[] { pos[0], pos[1] });
			visited[pos[0]][pos[1]] = true;
		}

		while (!queue.isEmpty()) {
			int[] now = queue.poll();
			int x = now[0], y = now[1];

			for (int[] w : way) {
				int nx = x + w[0], ny = y + w[1];
				if (!inRange(nx, ny) || visited[nx][ny])
					continue;
				if (box[nx][ny] == WALL)
					continue;
				visited[nx][ny] = true;
				depth[nx][ny] = depth[x][y] + 1;
				queue.add(new int[] { nx, ny });
			}
		}

		int maxDist = 0;

		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++) {
				if (box[i][j] == VIRUS) {
					if (visited[i][j])
						maxDist = Math.max(maxDist, depth[i][j]);
					else
						maxDist = Integer.MAX_VALUE;
				}
			}
		return maxDist;
	}

	static boolean inRange(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < N;
	}
}