백준 17142번 : 연구소3

 문제

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

17142 연구소3

 

 구현 방법

바이러스 중 어느 것을 활성화 해야 최소 시간이 걸리는지 모르기 때문에 모든 경우의 수를 확인해 주었습니다.
바이러스를 list에 담아 list index를 활용하여 조합을 돌렸습니다.
선택이 완료될 때마다 방문배열과 큐를 새로 생성하여 해당 경우의 최소 시간을 구했습니다.

 

세부적인 조건을 설명해보자면

1. 빈 칸 세기

바이러스가 칸을 전부 채우는지 확인이 필요합니다.

하지만 경우마다 NxN 배열을 다 확인하는 건 낭비라고 생각하였고 다르게 하는 방법이 없을까 생각했고 생각한 방법이 빈 칸 세기입니다.
맨 처음 배열에 값을 입력할 때 빈 칸 개수를 카운트했고, 경우마다 바이러스가 확장할 때 빈 칸을 채우는 카운트를 따로 세주었습니다.

빈 칸 개수와 빈 칸을 채우는 개수가 같으면 빈 칸이 없어졌다는 뜻이므로 반복문을 끝내주었다.

2. bfs 돌릴 때

최소 시간을 구해야 하기 때문에 해당 레벨만 검사했습니다.
주의할 점은 빈 칸을 채우는 개수를 카운트할 때 비활성화 바이러스는 포함하지 않아도 되므로 빈 칸 일때만 카운트를 세주었습니다.
사이즈만큼 반복문이 끝나면 빈 칸 개수와 빈 칸을 채우는 개수가 같을 때 true를 리턴했습니다.
또한 현재까지 구한 최소 시간보다 현재 경우의 시간이 더 커지면 최소 시간이 아니므로 false를 리턴했습니다.
큐를 돌리는 while문이 끝나면 빈 칸을 다 못채운 것 이므로 false를 리턴했습니다.

3. 결과 출력 시

빈 칸 개수가 0이면 이미 빈 칸이 없다는 의미기 때문에 바로 0을 출력했고
구한 최소 시간이 처음 초기화 했던 값과 같으면 빈 칸을 아예 못채웠으니 -1을 출력해주었고 아닐 시 구한 최소 시간을 출력했습니다.

 

 구현 코드

package BOJ.Gold;

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

public class BOJ17142_연구소3 {
	static int N, M, MIN, cntT, emptyCnt, transCnt;
	static int[][] map, deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static boolean[][] visit;
	static int[] select;
	static List<Virus> virus;
	static Queue<Virus> queue;
	static class Virus {
		int r, c;
		public Virus(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		select = new int[M];
		virus = new ArrayList<>();
		MIN = Integer.MAX_VALUE;
		for (int r=0;r<N;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<N;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
				if (map[r][c]==2) virus.add(new Virus(r, c)); // list에 바이러스 넣기
				else if (map[r][c]==0) emptyCnt++; // 빈 칸 세기
			}
		}
		if (emptyCnt==0) System.out.println(0);
		else {
			combination(0, 0);
			if(MIN == Integer.MAX_VALUE) System.out.println(-1);
			else System.out.println(MIN);
		}
		
	}
	
	static void combination(int cnt, int start) {
		if(cnt==M) {
			queue = new LinkedList<>();
			visit = new boolean[N][N];
			cntT = 0; transCnt = 0;
			for (int i=0;i<M;i++) {
				int r = virus.get(select[i]).r;
				int c = virus.get(select[i]).c;
				queue.offer(new Virus(r, c)); 
				visit[r][c] = true;
			}
			
			if(bfs()) MIN = Math.min(MIN, cntT+1);
			return;
		}
		
		for (int i=start;i<virus.size();i++) {
			select[cnt] = i;
			combination(cnt+1, i+1);
		}
	}
	
	static boolean bfs() {
		while(!queue.isEmpty()) {
			int size = queue.size();
			for (int s=0;s<size;s++) {
				Virus now = queue.poll();
				for (int d=0;d<4;d++) {
					int nr = now.r+deltas[d][0];
					int nc = now.c+deltas[d][1];
					if (isIn(nr, nc) && !visit[nr][nc] && map[nr][nc]!=1) {
						if(map[nr][nc]==0) transCnt++; // 해당 map이 빈 칸일 경우에만 빈 칸 채우는 카운트 ++
						queue.offer(new Virus(nr, nc));
						visit[nr][nc] = true;
					}
				}
			}
			if (transCnt==emptyCnt) return true;  // 빈 칸 채우는 카운트와 빈 칸 카운트가 같으면 true 리턴
			if (cntT++>=MIN) return false;;
		}
		return false;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<N && nc>=0 && nc<N;
	}
}

 

정답!