[백준] 17142 연구소3

1.문제

 

2. 접근 방법

단순 bfs를 활용한 완탐문제이다. 다만 존재하는 바이러스 중 M개의 바이러스만 선택해서 퍼쳐나가는데 그 중 가장 빠르게 전체에 퍼쳤을 때 몇 시간이 걸리는지 찾아내는 문제이다.

 

1. 그래서 전체 바이러스 갯수 중에 M개를 고르는 작업 (조합)

2. 골라논 바이러스를 퍼치는 작업(BFS)

//비활성 바이러스(맵에서 2)가 있는 위치는 퍼치지 않더라도 바이러스이니 굳이 거치지 않아도 된다.

3. 그 중 가장 빠르게 퍼쳤을 때의 시간이 얼마나 인지 찾는 작업(bfs rank가 가장 작은 것 찾아내기)

//다 퍼쳤는지 검사는 모든 맵을 검사할 필요 없이 0의 갯수를 세어놓고 바이러스가 0위치에 퍼질때마다 카운트 하면 쉽게 구할 수 있다.

 

아래 그림은 예제 1에서 조합으로 바이러스 조합을 하나씩 뽑아서 펼쳐 나가는 모습을 도식화 한 것.

 

 

 

 

3. 풀이

1. 2차원 배열에 맵 만들기

2. 바이러스의 갯수를 구해놓고 그 중 M개를 뽑는 조합 구하기

3. 조합이 구해지면 bfs를 활용해 모든 맵에 퍼치는데 몇 시간 걸리는지 구하기

4. 모든 조합에 대해 몇 시간이 걸리는지 구하고 그 중 최솟값 구하기

 

4. 자바코드

package 백준;

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.Queue;
import java.util.StringTokenizer;

//조합 bfs 날짜세기 짬뽕문제
public class P17142연구소3 {
	static boolean visit[][];
	static ArrayList<Point> virus = new ArrayList<Point>();
	static int N, V, zeroCnt, map[][];
	static int min = 123456789;
	static int dr[] = {1,0,-1,0};
	static int dc[] = {0,-1,0,1};
	static void comb(int[] sel, int sidx, int idx) {
		if(sidx == V) {
			visit = new boolean[N][N];
			BFS(sel);
			return;
		}
		if(idx == virus.size())
			return;
		
		sel[sidx] = idx;
		comb(sel,sidx+1,idx+1);
		comb(sel,sidx,idx+1);
		
	}
	
	static void BFS(int sel[]) {
		Queue<Point> que = new LinkedList<Point>();
		for(int i : sel) {
			Point v = virus.get(i);
			que.offer(v);
			visit[v.x][v.y] = true;
		}
		que.offer(new Point(-1,-1));
		int cnt = 0;
		int time = 0;
		while(true) {
			Point p = que.poll();
			if(p.x == -1) {
				if(que.isEmpty())
					break;
				time++;
				que.offer(new Point(-1,-1));
				continue;
			}
			if(map[p.x][p.y] == 0) { 
				cnt++;
			}
			if(cnt == zeroCnt) {
				min = Math.min(min, time);
				break;
			}
			for(int i = 0 ; i < 4 ; i++) {
				int row = p.x+dr[i];
				int col = p.y+dc[i];
				if(row<0 || col<0 || row>=N || col >= N)
					continue;
				if(visit[row][col])
					continue;
				if(map[row][col] == 1)
					continue;
				
				visit[row][col] = true;
				que.offer(new Point(row,col));
			}
			
				
			
			
		}
		
		
		
	}
	
	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());
		V = Integer.parseInt(st.nextToken());
		map = new int [N][N];
		visit = new boolean[N][N];
		zeroCnt = 0;
		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] == 0)
					zeroCnt++; //0의 갯수 세어 놓기
				if (map[i][j] == 2)
					virus.add(new Point(i, j)); //바이러스의 위치
			}
		}
		
		comb(new int[V], 0, 0);
		if(min == 123456789)
			min = -1;
		
		System.out.println(min);
		
	}

}

5. 마치며

하나하나 보면 그렇게 구현 난이도가 높지는 않은데 여러가지를 짬뽕해서 풀어야 해

조금 복잡복잡했던 문제였다. 문제를 많이 풀어봤었다면 어렵지 않게 풀 수 있을 것 같다.

 

17142번: 연구소 3