BOJ - 17142 연구소3

17142 연구소 3 : https://www.acmicpc.net/problem/17142

---

Problem

---

Solve

M개의 바이러스를 재귀를 통해 선택하고 선택한 바이러스가 동시에 퍼져서 연구소 배열의 빈칸을 채우는데까지 걸리는 시간을 구하기 위해 BFS를 사용하면된다.

바이러스가 퍼지는데 까지 걸리는 시간은 사방으로 퍼질 바이러스를 담을 Queue가 퍼질때 연구소에 있는 0의 개수에 유의하면서 퍼트리고 현재 시간에 퍼질 바이러스 모두 퍼트렸을때 시간을 +1씩 카운트 하면서 연구소의 0의 개수가 0이 된다면 카운트된 시간을 반환하고, 0이 되지 않았는데 더이상 바이러스를 퍼트릴수 없다면 -1을 반환한다.
이 때 바이러스를 퍼트리는 함수에서 -1이 반환되었을 때 다른 바이러스를 선택했을 경우도 생각해야하므로 기존 비교값을 유지한다. 단, 모든 바이러스 선택의 경우의수를 확인해도 기존 비교값을 유지하고 있다면 -1을 반환한다.

BFS를 사용해서 바이러스를 퍼트릴때 비활성화되어있는 바이러스에 접근하게 되면 활성바이러스가 되지만 문제에서 요구하는 것은 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력하는 것임을 유의하면서 구현한다.

---

Code

public class 연구소3 {
	static int N;
	static int M;
	static int[][] map;
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, -1, 0, 1};
	static List<Virus> virusList;
	static Virus[] activeVirus;
	static int spaceCount;
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		virusList = new ArrayList<>();
		activeVirus = new Virus[M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0)
                	//연구소 배열안 0의 개수 갱신
					spaceCount++;
				else if (map[i][j] == 2)
                	//연구소 배열안 바이러스 위치 추가
					virusList.add(new Virus(i, j));
			}
		}

		//연구소 배열안 0의 개수가 없다면 이미 바이러스가 퍼질수 없는 상태이므로 0을 반환.
		if (spaceCount == 0) {
			answer = 0;
		} else {
			answer = Integer.MAX_VALUE;
			choiceVirus(0, 0);
            //answer값이 유지되어있다면 모든 경우의 수도 연구소를 바이러스로 채울수 없다.
			answer = answer == Integer.MAX_VALUE ? -1 : answer;
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	//바이러스 유출
	static int spreadVirus() {
		Queue<Virus> queue = new LinkedList<>();
		boolean[][] visit = new boolean[N][N];

		//활성화되어 있는 바이러스 M개 queue에 초기화
		for (Virus v : activeVirus) {
			queue.add(new Virus(v.y,v.x));
			visit[v.y][v.x] = true;
		}
        //유출하는데 걸리는 총 시간
		int time = 0;
		int subSpaceCount = spaceCount;
		while (!queue.isEmpty()) {
			int size = queue.size();

			//현재 시간에 퍼질 바이러스들
			for (int i = 0; i < size; i++) {
				Virus current = queue.poll();

				//상하좌우 이동
				for(int j=0;j<4;j++){
					int ny = current.y+dy[j];
					int nx = current.x+dx[j];

					if(ny>=0 && nx>=0 && ny<N && nx<N && !visit[ny][nx] && (map[ny][nx]==0 || map[ny][nx]==2)){
						visit[ny][nx] = true;
						queue.add(new Virus(ny,nx));
                        //바이러스가 퍼진 곳이 0이라면 연구소 배열안 0의 개수 차감
						if(map[ny][nx] == 0) subSpaceCount--;
					}
				}
			}
            //현재 시간에 퍼질 바이러스가 모두 퍼졌다면 시간 추가
			time++;

			//연구소 배열안이 빈공간이 없어졌다면 현재 시간 반환.
			if(subSpaceCount == 0){
				return time;
			}
		}
		return -1;
	}

	//재귀로 바이러스 M개 선택
	static void choiceVirus(int idx, int dept) {
		if (dept == M) {
			int takeTime = spreadVirus();
			if(takeTime != -1){
				answer = Math.min(answer, takeTime);
			}
			return;
		}

		for (int i = idx; i < virusList.size(); i++) {
			activeVirus[dept] = virusList.get(i);
			choiceVirus(i+1, dept+1);
		}
	}

	static class Virus {
		int y;
		int x;

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

---

Result

---

Reference

https://loosie.tistory.com/261