Baekjoon_17142_연구소3

문제 설명

17142번: 연구소 3

• 입력으로 제공되는 연구소의 배치 중 2의 위치에 비활성 바이러스가 위치함
• 비활성 바이러스 중 M개를 활성 바이러스로 변경
• 바이러스는 동시에 상, 하, 좌, 우로 퍼지고, 그 과정은 1초가 소요됨
• 1은 벽이므로 바이러스를 퍼뜨릴 수 없음
• 활성 바이러스가 비활성 바이러스의 칸으로 가면 비활성 바이러스는 활성화됨

=> 연구소에 바이러스를 전부 퍼뜨리는데 걸리는 최소 시간 출력 (전부 퍼뜨리지 못할 경우 -1 출력)

 

 

문제 풀이

Baekjoon_17141_연구소2

이 문제는 앞서 푼 연구소2 문제와 유사하지만, 특정 위치에 바이러스를 위치시켰던 연구소2와는 다르게 비활성 바이러스를 두고 M개의 바이러스만 활성화시킨다는 점이 다르다.

 

문제는 연구소의 모든 빈 공간에 바이러스를 퍼뜨리는 최소 시간을 출력하는 것이고, 조건에 따르면 2의 위치에 비활성 바이러스가 위치해 있으므로 활성 바이러스가 비활성 바이러스의 위치에 오는 것은 시간에 영향이 가지 않아야 한다.(빈 칸에 바이러스를 퍼뜨리는 것이 아니니)

 

따라서 이 조건을 추가하여 문제를 해결하기 위해 meetZero 변수와 prevMeetVirus변수를 새로 추가했다.

 

meetZero : 이번 시간에 0번 칸에 바이러스를 퍼뜨렸는지 확인하는 변수

prevMeetVirus : 이전 턴에 비활성 바이러스를 활성화 시켰는지

 

meetZero변수를 이용해 0번 칸에 바이러스를 퍼뜨렸을 때에만 시간이 추가되도록 했다.

 

0번 칸을 만나지 않았음에도 큐가 비어있지 않은 채라면 prevMeetVirus 변수를 true로 처리했는데 이는 2번칸, 즉 비활성 바이러스만을 만났다는 의미이다.

 

prevMeetVirus변수와 meetZero변수를 이용해 이전 턴에서 비활성 바이러스를 활성화 시켰으면서 이번 턴에 0번 칸에 바이러스를 퍼뜨렸다면 새로 활성화된 바이러스가 빈 칸을 채운 것을 의미하므로 시간을 1초 늘려주었다.

 

문제 풀이 코드

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

public class _17142_연구소3 {
	static class Node {
		int r, c;

		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static int N, M, map[][], minTime = Integer.MAX_VALUE, zeros = 0;
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };
	static Node choice[];
	static ArrayList<Node> viruses = new ArrayList<>();
	static boolean canFill = false;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		choice = new Node[M];
		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0)
					++zeros;
				else if (map[i][j] == 2) {
					viruses.add(new Node(i, j));
				}
			}
		}
		Comb(0, 0);
		if (canFill)
			System.out.println(minTime);
		else
			System.out.println(-1);

	}

	static void Comb(int idx, int count) {
		if (count == M) {
			bfs();
			return;
		}

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

		choice[count] = viruses.get(idx);
		Comb(idx + 1, count + 1);
		Comb(idx + 1, count);
	}

	static void bfs() {
		int time = 0;
		int count = 0;
		boolean visited[][] = new boolean[N][N];
		Queue<Node> q = new LinkedList<>();
		for (int i = 0; i < M; ++i) {
			Node n = choice[i];
			visited[n.r][n.c] = true;
			q.add(n);
		}
		boolean meetZero = false;		//0번 칸에 바이러스를 퍼뜨렸는지
		boolean prevMeetVirus = false;	//이전 시간에 비활성바이러스를 활성화시켰는지
		while (!q.isEmpty()) {
			int size = q.size();
			if (time >= minTime) {
				return;
			}
			meetZero = false;
			while (--size >= 0) {
				Node n = q.poll();
				for (int i = 0; i < 4; ++i) {
					int rr = n.r + dr[i];
					int cc = n.c + dc[i];

					if (rr < 0 || cc < 0 || rr >= N || cc >= N) // 범위 밖에 나갈 경우
						continue;
					if (visited[rr][cc]) // 이미 방문한 곳일 경우
						continue;
					if (map[rr][cc] == 1) // 벽이 위치한 곳일 경우
						continue;

					visited[rr][cc] = true;
					q.add(new Node(rr, cc));
					if (map[rr][cc] == 0) {
						++count;
						meetZero = true;
					}
				}
			}
			
			if(prevMeetVirus) {	//이전에 활성화 시켰으면서
				if(meetZero) {	//이번에 0인 자리를 1로 바꾸었다면
					++time;		//1초 추가
				}
				prevMeetVirus = false;
			}
			if(meetZero) {
				++time;
			}else {	//0을 만나지 않은 경우 비활성 바이러스를 만난 것.
				prevMeetVirus = true;
			}
		}
		
		if (zeros == count) {
			canFill = true;
			minTime = Math.min(minTime, meetZero?time-1:time);	//마지막 바이러스는 퍼지지 않았으므로 1초 제외한다.
		}

	}

}