백준 17142 - 연구소 3

Java

17142 번 - 연구소 3

문제

접근 방법

DFS와 BFS의 사용법을 묻는 문제였다. 연구소의 정보를 받아, 바이러스를 놓을 수 있는 공간의 정보들을 List에 저장한다.
이후 DFS로 M개의 바이러스를 놓을 위치를 정한다.

정한 바이러스 위치에 3이라고 따로 활성화 된 바이러스라고 갱신한 후, BFS로 퍼뜨린다.

BFS로 퍼뜨릴 때 마다 시간을 증가시켜, 그 시간을 출력한다.

주의 할 점이, 바이러스는 빈 공간 0과 활성화 되지 않은 바이러스 2에 퍼질 수 있다.
만약, 빈 공간 0에 바이러스가 덮여있는데, 활성화 되지 않은 바이러스가 남아있으면 그 바이러스에도 퍼져 시간이 흐른 것 처럼 오류가 발생한다.
따라서, 처음 빈 공간의 수를 세어 빈 공간에 바이러스가 퍼질 때 마다, 빈 공간의 수를 줄인다.
이 남은 빈 공간의 수를 이용하여, 만약 더 이상 바이러스가 퍼질 빈 공간이 없을 때는 활성화 되지 않은 바이러스에 바이러스가 퍼져도 시간이 증가하지 않게 하였다.

또한, 위의 빈 공간의 수를 이용하여, 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우를 판단하였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result = Integer.MAX_VALUE, lastNum;
	static int[][] lab, copy;
	static List<int[]> virus;
	static boolean[] vis;
	static int cntV;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	lab = new int[n][n];
    	copy = new int[n][n];
    	virus = new ArrayList<int[]>();
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			lab[i][j] = stoi(stk.nextToken());
    			if(lab[i][j] == 2) {
    				virus.add(new int[] {i,j});
    			}
    			else if(lab[i][j] == 0) {
    				lastNum++;
    			}
    		}
    	}
    	cntV = virus.size();
    	vis = new boolean[cntV];


    	DFS(0, 0);

    	if(result != Integer.MAX_VALUE)
    		System.out.println(result);
    	else
    		System.out.println(-1);

    	br.close();
	}
	// 활성화 할 바이러스 선택
	static void DFS(int lv, int start) {
		if(lv == m) {
			// 연구소 복사
			for(int i = 0; i < n; i++)
				copy[i] = lab[i].clone();

			// 활성화 바이러스 등록
			int y,x;
			Queue<int[]> q = new LinkedList<int[]>();
			for(int i = 0; i < cntV; i++) {
				if(vis[i]) {
					y = virus.get(i)[0];
					x = virus.get(i)[1];
					copy[y][x] = 3;
					q.add(new int[] {y,x});
				}
			}

			result = Math.min(result, BFS(q, lastNum));

			return;
		}

		for(int i = start; i < cntV; i++) {
			if(!vis[i]) {
				vis[i] = true;
				DFS(lv + 1, i + 1);
				vis[i] = false;
			}
		}

	}

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

	private static int BFS(Queue<int[]> queue, int vacantN) {

		int y,x,ny,nx;
		int time = 0, size = 0;
		int[] q;
		boolean isSpread = false;
		while(!queue.isEmpty()) {
			size = queue.size();
			isSpread = false;

			for(int idx = 0 ; idx < size; idx++) {
				q = queue.poll();
				y = q[0];
				x = q[1];

				for(int i = 0; i < 4; i++) {
					ny = y + dy[i];
					nx = x + dx[i];

					if(isIn(ny,nx) && copy[ny][nx] != 3 && copy[ny][nx] != 1) {
						if(copy[ny][nx] == 0) {
							vacantN--;	// 빈 공간의 수 줄여준다.
							isSpread = true;
						}
						else {
							if(vacantN != 0) {	// 빈 공간이 없으면, 더 이상 퍼지는 시간을 증가하지 않는다.
								isSpread = true;
							}
						}
						copy[ny][nx] = 3;
						queue.add(new int[] {ny,nx});
					}
				}
			}

			if(isSpread) {	// 한 번이라도 바이러스가 퍼졌을 때
				time++;
			}
		}

		if(vacantN != 0)		// 빈 공간이 남아 있으면
			return Integer.MAX_VALUE;

		return time;
	}

	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= n)
            return false;
        return true;
    }

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

반례를 확인하여, 틀렸다는 것을 알아챘던 문제

개선할 점