[백준] 17141 연구소2 (Java)

[17141 연구소2]

난이도: 골드4

17141번: 연구소 2

문제

입력

출력

---

[아이디어]

바이러스가 들어갈 자리에서 M개를 조합으로 선택하여 완전 탐색하는 방법이다.

사방면으로 바이러스가 퍼져나갈 수 있고, 최소 시간을 구하는 문제이기 때문에 BFS를 사용하였다.

 

그 외는 단순한데, Queue에 처음 바이러스 자리 M개를 초기화 시켜줄 때 전체 맵을 탐색할지 M개를 바로 넣을지를 고민하였다. 직접 해본 시간이 별로 차이나지 않으므로 아무거나 써도 될 것 같다!

---

[JAVA 코드]

1. M개를 바로 초기화

// 메모리: 41388KB
// 시간: 220ms

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, M, result = Integer.MAX_VALUE;
	static int [][] map;
	static int [] selected;
	static List<Point> virus;
	static Queue<Point> Q;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	
	static class Point {
		int r, c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		
		map = new int [N][N];
		virus = new ArrayList<>();
		for(int r = 0; r < N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 0; c < N; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
				
				if(map[r][c] == 2) {
					map[r][c] = 0;
					virus.add(new Point(r, c));
				} 
				if(map[r][c] == 1) {
					map[r][c] = -1; // 벽은 -1로 표시
				}
			}
		}
		
		selected = new int [M];
		comb(0, 0);
		
		if(result == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(result);
	}

	// 바이러스가 들어갈 수 있는 자리에 M개의 바이러스를 조합으로 넣어주기
	private static void comb(int start, int cnt) {
		if(cnt == M) {
			result = Math.min(result, countTime());
			return;
		}
		
		for(int i = start; i < virus.size(); i++) {
			map[virus.get(i).r][virus.get(i).c] = 2;
			selected[cnt] = i; // i번째 바이러스 자리 선택
			comb(i + 1, cnt + 1);
			map[virus.get(i).r][virus.get(i).c] = 0;
		}
	}

	// 최대 시간 찾아주기
	private static int countTime() {
		int [][] time = new int [N][N];
		Q = new LinkedList<>();

		// 바이러스 위치 초기화
		for(int i = 0; i < M; i++) {
			Q.offer(virus.get(selected[i]));
		}
		
		// BFS
		while(!Q.isEmpty()) {
			Point now = Q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nr = now.r + dr[i];
				int nc = now.c + dc[i];
				
				// 인덱스를 벗어나거나 빈칸이 아닌 경우
				if(nr < 0 || nr >= N || nc < 0 || nc >= N ) continue;
				if(map[nr][nc] != 0 || time[nr][nc] != 0) continue;
				
				Q.offer(new Point(nr, nc));
				time[nr][nc] = time[now.r][now.c]+ 1; 
			}
		}
		
		// 최대 걸린 시간 찾기
		int maxTime = 0;
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < N; c++) {
				// 벽인경우
				if(map[r][c] == -1) continue;
				
				// 바이러스가 다 퍼지지 못한 경우
				if(time[r][c] == 0 && map[r][c] == 0) {
					return Integer.MAX_VALUE;
				}
				
				maxTime = Math.max(maxTime, time[r][c]);
			}
		}
		
		return maxTime;
	}

}

 

2. 전체 맵 탐색

// 메모리: 41740KB
// 시간: 240ms

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, M, result = Integer.MAX_VALUE;
	static int [][] map;
	static List<Point> virus;
	static Queue<Point> Q;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	
	static class Point {
		int r, c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		
		map = new int [N][N];
		virus = new ArrayList<>();
		for(int r = 0; r < N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 0; c < N; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
				
				if(map[r][c] == 2) {
					map[r][c] = 0;
					virus.add(new Point(r, c));
				} 
				if(map[r][c] == 1) {
					map[r][c] = -1; // 벽은 -1로 표시
				}
			}
		}
		
		comb(0, 0);
		if(result == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(result);
	}

	private static void comb(int start, int cnt) {
		if(cnt == M) {
			result = Math.min(result, countTime());
			return;
		}
		
		for(int i = start; i < virus.size(); i++) {
			map[virus.get(i).r][virus.get(i).c] = 2;
			comb(i + 1, cnt + 1);
			map[virus.get(i).r][virus.get(i).c] = 0;
		}
	}

	private static int countTime() {
		int [][] time = new int [N][N];
		Q = new LinkedList<>();
		
        	// 바이러스 위치 초기화
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < N; c++) {
				if(map[r][c] == 2) {
					Q.offer(new Point(r, c));
				}
			}
		}
		
		while(!Q.isEmpty()) {
			Point now = Q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nr = now.r + dr[i];
				int nc = now.c + dc[i];
				
				// 인덱스를 벗어나거나 빈칸이 아닌 경우
				if(nr < 0 || nr >= N || nc < 0 || nc >= N ) continue;
				if(map[nr][nc] != 0 || time[nr][nc] != 0) continue;
				
				Q.offer(new Point(nr, nc));
				time[nr][nc] = time[now.r][now.c]+ 1; 
			}
		}
		
		int maxTime = 0;
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < N; c++) {
				// 벽인경우
				if(map[r][c] == -1) continue;
				
				// 바이러스가 다 퍼지지 못한 경우
				if(time[r][c] == 0 && map[r][c] == 0) {
					return Integer.MAX_VALUE;
				}
				
				maxTime = Math.max(maxTime, time[r][c]);
			}
		}
		
		return maxTime;
	}

}