[백준] 17141. 연구소2 (자바 JAVA)

[ 문제 ]  [백준] 17141. 연구소2 

 

문제 링크 : https://www.acmicpc.net/problem/17141

17141번: 연구소 2

---

# 접근 방법 및 풀이 

 

• 구현 + bfs로 풀었다. 
• 1. 0인 빈칸 갯수 세기 -> bfs 돌려서 빈칸에 퍼질때마다 카운트를 -1 할거다.
• 2. 바이러스를 놓을 수 있는 곳이 최대 10개 이므로, 조합으로 바이러스 놓을 곳 M개 뽑기
• 3. BFS로 바이러스 퍼트리기
• 큐에 선택한 바이러스 좌표를 다 넣고 bfs 돌려서 큐에서 마지막으로 나온 바이러스가 최종 퍼진 시간이다.
• 해당 시간의 최솟값을 구해서 ans에 넣으면 끝!

# 주의할 점 

 

• 바이러스는 1 벽이 아닌 곳에 퍼질 수 있다 -> 0과 2에 퍼질 수 있다. 즉, 빈칸과 바이러스를 놓을 수 있는 곳에 퍼질 수 있으므로, 0빈칸에 퍼질 경우만 zero카운트를 -1씩 해준다.
• 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력해야하므로, zero가 0이 아닐 경우는 제외해야한다!

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj17141_연구소2 {
	static int N, M, map[][], zeroCnt = 0, ans = Integer.MAX_VALUE;
	static List<Point> list;
	static Point sel[];
	static class birus{
		int r, c, time;
		public birus(int r, int c, int time) {
			this.r = r;
			this.c = c;
			this.time = time;
		}
	}
	static int dr[] = {-1, 1, 0, 0};
	static int dc[] = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		list = new ArrayList<Point>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 0)
					zeroCnt ++;
				if(map[i][j] == 2)
					list.add(new Point(i, j));
			}
		}
		sel = new Point[M];
		comb(0, 0);
		System.out.println((ans==Integer.MAX_VALUE)? -1 : ans);
	}
	private static void comb(int idx, int s_idx) {
		if(s_idx == M) {
			bfs();
			return;
		}
		if(idx == list.size())
			return;
		sel[s_idx] = list.get(idx);
		comb(idx+1, s_idx+1);
		comb(idx+1, s_idx);
	}
	
	private static void bfs() {
		int zero = zeroCnt;
		boolean visit[][] = new boolean[N][N];
		Queue<birus> queue = new LinkedList<birus>();
		for (int i = 0; i < M; i++) {
			visit[sel[i].x][sel[i].y] = true;
			queue.add(new birus(sel[i].x, sel[i].y, 0));
		}
		int time = 0;
		while(!queue.isEmpty()) {
			birus b = queue.poll();
			time = b.time;
			for (int d = 0; d < 4; d++) {
				int nr = b.r + dr[d];
				int nc = b.c + dc[d];
				if(nr < 0 || nc < 0 || nr >= N || nc >= N || visit[nr][nc] || map[nr][nc] == 1)
					continue;
				visit[nr][nc] = true;
				queue.add(new birus(nr, nc, b.time+1));
				if(map[nr][nc] == 0)
					zero --;
			}
		}
		if(zero == 0) {
			ans = Math.min(ans, time);
		}
	}
}

 

 

REVIEW

연구소 시리즈는 좋은 문제다.