백준 17142번: 연구소 3

문제 설명

• 바이러스는 벽을 통과하지 못하며 상,하,좌,우로 움직입니다.
• 여러 바이러스 중 M개의 바이러스만 활성 상태로 변경합니다.
• 활성상태의 바이러스는 1초에 한칸씩 확산됩니다.
• 모든 공간이 바이러스(활성,비활성 구분 없이)로 채워지는 시간을 구해야 합니다.

접근법

• M개의 활성 바이러스를 선택하지 위해 조합을 구현했습니다.
• 바이러스의 확산을 표현하기 위해 BFS를 구현했습니다.
• 여러번 실험을 진행해야 하기 때문에 원본board가 아닌 CopyBoard를 활용했습니다.
  • CopyBoard는 상당한 메모리를 차지합니다. 여기에다 방문처리 배열까지 사용하면 메모리 초과가 발생합니다.
• M개의 조합 중 모든 공간을 바이러스로 채우는 조합과, 그렇지 못한 조합이 섞여 있을 수 있습니다.
  • 어느 한 조합이 모든 공간을 채우지 못했다고 해서 곧바로 -1을 반환하면 안됩니다.
    • -1은 최솟값을 도출하는 Math.min함수에서 모든 양수인 결과값을 무시하게 됩니다.

pseudocode

Main(){
	M개의 바이러스를 실행하는 모든 조합 comb를 실행합니다.
    최종 시간을 계산합니다.    
}
comb(){
	if(M개의 조합이 완성되면){
    	q에 M개의 pos조합을 넣습니다.
        입력값으로 만든 2차원 배열 Board를 복사한 CopyBoard를 만듭니다.
        CopyBoard와 q로 BFS를 수행합니다.
    }
}
BFS(q,board){
	while(q에 값이 존재하지 않을 때까지){
    	while(현재의 q가 0이 될 때 까지){ // 같은 depth의 좌표들이 동시에 실행됩니다.
        	q의 값을 하나씩 꺼내어 4방탐색을 진행합니다.
            4방의 좌표 중 벽이 아니면서 아직 방문하지 않은 곳이면
            해당 좌표를 방문합니다.
        }
        현재 depth에서 모든 공간이 바이러스로 채워졌는지(0이 존재하지 않는지) 확인합니다. 
    }
    방문할 수 있는 모든 곳을 방문했는데도 0이 존재한다면 해당 조합으로는 모든 공간을 채우지 못하는 상황입니다.
}

ExistZero(board){
	0이 존재하면 true를, 그렇지 않으면 false를 반환합니다.
}

정답

import java.util.*;

public class Main {
	static int N, M;
	static int[] ans;
	static List<pos> lst;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int MinVal = Integer.MAX_VALUE;
	static int[][] board;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		ans = new int[M];
		board = new int[N][N];
		lst = new ArrayList<pos>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int val = sc.nextInt();
				if (val == 2) {
					lst.add(new pos(i, j));
					board[i][j] = 99; // 바이러스 위치
				} else if (val == 1) {
					board[i][j] = 999; // 벽 위치
				} else {
					board[i][j] = val;
				}
			}
		}

		comb(0, 0, board);
		if (MinVal == 9998) {
			System.out.println(-1);
		} else if (!ExistZero(board)) {
			System.out.println(0);
		} else {
			System.out.println(MinVal);
		}

	}

	public static void comb(int depth, int start, int[][] board) {
		if (depth == M) {
			Queue<pos> q = new LinkedList<pos>();
			for (int i = 0; i < M; i++) {
				q.add(lst.get(ans[i]));
			}
			int[][] CopyBoard = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					CopyBoard[i][j] = new Integer(board[i][j]);
				}
			}

			// CopyBoard에 Visited배열까지 사용해서 메모리 초과가 발생했었습니다.
			MinVal = Math.min(MinVal, BFS(q, CopyBoard));

			return;
		}
		for (int i = start; i < lst.size(); i++) {
			ans[depth] = i;
			comb(depth + 1, i + 1, board);
		}

	}

	public static int BFS(Queue<pos> q, int[][] board) {
		int cnt = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			cnt++;
			while (--size >= 0) {
				pos val = q.poll();
				for (int d = 0; d < 4; d++) {
					int nx = val.x + dx[d];
					int ny = val.y + dy[d];
					// 아직 방문하지 않은 길과 비활성 바이러스가 있는 곳을 지나갈 수 있습니다.
					if (0 <= nx && nx < N && 0 <= ny && ny < N && (board[nx][ny] == 0 || board[nx][ny] == 99)) {
						q.add(new pos(nx, ny));
						board[nx][ny] = cnt;
					}
				}
				if (!ExistZero(board)) {
					return cnt;
				}
			}
		}
		// 모든 칸에 바이러스를 퍼뜨릴 수 없는 경우를 체크하기 위한 구간입니다.
		// 곧바로 -1을 return하면 다른 경우의 수를 고려할 수 없습니다.
		// ex) A,B,C를 선택했을 때 모든 칸에 바이러스를 퍼뜨리지 못했습니다. -> 만약 -1을 return하면
		// 이후 B,C,D를 선택해서 5초만에 바이러스를 퍼뜨렸어도 -> Math.min(5,-1)이 되어 5초에 바이러스를 퍼뜨렸다는 결과를 얻지
		// 못합니다.
		if (ExistZero(board)) {
			return 9998;
		}
		return 9999; // 실행되지 않는 코드입니다.
	}

	public static boolean ExistZero(int[][] board) { // 배열에 0이 존재하는지 확인합니다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] == 0)
					return true;
			}
		}
		return false;
	}

	static class pos {
		int x;
		int y;

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

		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}

	}
}