[JAVA] 백준 17141 : 연구소 2

문제

17141번: 연구소 2

 

해결방법

오랜만에 BFS 탐색 문제이다.

이 문제의 경우 연구소에 특정 위치에 바이러스를 놓아서 연구소 전체를 바이러스에 감염시키려는 승원이의 계획을 도와주는 문제이다.

 

문제에서 맵에 2로 표시된 구역이 바이러스를 놓을 수 있는 공간인데, 그 공간 중 M만큼 바이러스를 놓았을 때 연구소 전체를 감염시킬 수 있는 가장 빠른 시간을 구해야 한다.

즉, 모든 경우의 수를 탐색해야 하는 완전 탐색 문제라고도 할 수 있다.

 

조합을 찾을 때는 비트 마스킹을 사용해서 방문 처리를 해주었다.

또 조합을 찾았을 때 해당 조합에서 바이러스가 퍼지는 경우를 탐색할 때 새로 맵을 만들어야 하는데, 그럴 때마다 기존의 맵을 이중 for문을 사용해서 복제하는 것은 너무 비효율적이라고 생각해 벽 위치가 담겨있는 ArrayList를 만들어두고 새로운 맵을 만들 때 해당 벽 위치만 입력해주었다.

그리고 바이러스를 완전히 퍼뜨렸는지 여부를 체크하기 위해 빈 공간의 개수를 확인할 blankCnt를 선언해두고, 바이러스를 퍼뜨리면서 바이러스 개수를 카운트해서 두 개가 일치하면 모든 공간이 바이러스로 가득 찼다는 것을 의미해서 걸린 시간을 리턴하고 아니라면 Integer.MAX_VALUE를 통해 최댓값을 리턴해 해당 경우가 불가능함을 표시하였다.

 

코드를 구성한 순서는 다음과 같다.

• 바이러스를 놓을 수 있는 곳 중 M만큼 놓는 경우를 찾는다.
• 해당 경우를 탐색하기 위한 맵을 새로 만든다.
• 새로 만든 맵에서 바이러스를 퍼뜨려보고 모든 공간에 바이러스가 퍼졌다면 걸린 시간을 리턴한다.
• 모든 경우의 수를 찾아보고 가장 빨리 퍼뜨린 시간을 출력한다.

 

코드에 자세하게 주석을 달아놓았으니 참고해주길 바란다.

 

코드

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 Main_G4_17141 {
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	static int N, M, map[][], blankCnt, result;
	static ArrayList<Node> canVirus = new ArrayList<>(); // 바이러스를 놓을 수 있는 위치
	static ArrayList<Node> walls = new ArrayList<>(); // 벽의 위치
	
	static int[] combi; // 바이러스를 놓을 수 있는 조합

	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];
		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] == 1) walls.add(new Node(i, j)); // 벽 위치 체크
				else blankCnt++; // 벽이 아니면 빈 공간이므로 빈 공간 개수 증가
				
				if (map[i][j] == 2) { // 바이러스를 놓을 수 있는 공간
					canVirus.add(new Node(i, j));
					map[i][j] = 0; // 바이러스를 놓을 수 있는 공간은 빈 공간인 0으로 바꿔줌
				}
			}
		}

		combi = new int[M];
		result = Integer.MAX_VALUE;
		combination(0, 0, 0); // 조합을 돌려 계산
		
		if (result == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(result);
		
	}
	
	// 바이러스를 놓을 수 있는 조합 찾기
	static void combination(int start, int cnt, int flag) {
		// 탐색 완료
		if (cnt == M) {
			// 해당 조합에서 바이러스가 모두 퍼지는 시간 확인
			result = Math.min(result, goVirus());
			return;
		}

		// 비트마스킹을 이용한 조합 찾기
		for (int i = start; i < canVirus.size(); i++) {
			if ((flag & (1 << i)) == 0) {
				combi[cnt] = i;
				combination(i + 1, cnt + 1, flag | 1 << i);
			}
		}
	}
	
	// 바이러스 퍼뜨리기
	static int goVirus() {
		// bfs 탐색할 맵을 새로 구성
		int[][] useMap = new int[N][N];
		for (Node wall : walls) useMap[wall.r][wall.c] = 1; 
		
		// bfs 시작
		Queue<Node> q = new LinkedList<>();
		for (int idx : combi) {
			// 바이러스를 맵에 등록
			q.offer(canVirus.get(idx));
			useMap[canVirus.get(idx).r][canVirus.get(idx).c] = 2;
		}
		
		int virusCnt = 0; // 빈칸을 바이러스로 채운 개수
		int sec = -1; // 시간 체크
		
		while (!q.isEmpty()) {
			sec++; // 1초 증가
			
			// 현재 시간에 해당하는 바이러스들만 퍼뜨림
			int size = q.size(); 
			for (int i = 0; i < size; i++) {
				Node virus = q.poll();
				virusCnt++;
				
				for (int d = 0; d < 4; d++) {
					int nr = virus.r + dr[d];
					int nc = virus.c + dc[d];
					
					if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
					if (useMap[nr][nc] == 0) {
						q.offer(new Node(nr, nc));
						useMap[nr][nc] = 2;
					}
				}
			}
		}
		
		// 빈 칸을 모두 바이러스로 채웠는지 확인
		if (blankCnt == virusCnt) return sec;
		else return Integer.MAX_VALUE;
	}
	
	static class Node {
		int r;
		int c;
		
		Node (int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
}