ShinJongPark | Sean P
  • May 06, 2020

[삼성기출]백준17142 - 연구소3

 
by 박신종

이 문제는 조합과 bfs 알고리즘을 활용하여 풀었습니다.

주의 해야할 사항은

Input >>
4 2
0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0

Output >>
2

와 같이 바이러스의 활성상태와 비활성상태의 전환인데요.

문제를 잘 읽어볼 필요가 있습니다.

~. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

따라서 위와같은 케이스에서 처리를 해줘야 합니다.

소스는 다음과 같습니다.


package sw;

import java.io.*;
import java.util.*;
public class Main17142_연구소3 {
	
	static int N,M,V,E;
	static int[][] map;
	static int[][] dir = // 우하좌상
	static List<Pos> virusTotal;
	static List<Pos> virusSelect;
	static boolean[][] visit;
	static boolean check(int x, int y) {
		if(x>=0 && x<N && y>=0 && y<N)
			return true;
		else return false;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().trim().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		
		virusTotal = new ArrayList<>();
		virusSelect = new ArrayList<>();
		map = new int[N][N];
		V = 0;
		String[] str = null;
		for(int i=0; i<N; i++) {
			str = br.readLine().trim().split(" ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(str[j]);
				if(map[i][j]==2){
					virusTotal.add(new Pos(i,j));
					V++; 					// 총 바이러스 갯수 계산.
				}else if(map[i][j]==0) E++;	// bfs로 돌면서 공백의 갯수가 남아있을 때를 위해 계산.
			}
		}
		/*
		 * vCm
		 */
		combination(0);
		System.out.println(res==Integer.MAX_VALUE?-1:res);
	}
	
	static int res = Integer.MAX_VALUE,tmp;
	static void combination(int n) {
		if(virusSelect.size() == M) {
			tmp = bfs();
			if(res > tmp) res = tmp;
			return;
		}
		if(n == V) return;
		
		virusSelect.add(virusTotal.get(n));
		combination(n+1);
		virusSelect.remove(virusSelect.size()-1);
		combination(n+1);
	}
	
    static int bfs() {
		/*
		 * 선택된 바이러스로 bfs돌려서 최종 사이클(c)을 구합니다.
		 */
		Queue<Pos> qu = new LinkedList<>();
		visit = new boolean[N][N];
		Pos p = null;
		int e = E;
		int c = 0; // cycle
		int size = 0;
		if(e==0) return 0; // 빈공간이 없으므로 0 리턴.
		for(int i=0; i<M; i++) {
			p = virusSelect.get(i);
			visit[p.x][p.y] = true;
			qu.add(p);
		}
		int dx,dy;
		while(!qu.isEmpty()) {
			size = qu.size();
			for(int i=0; i<size; i++) {
				p = qu.poll();
				for(int d=0; d<4; d++){
					dx = p.x + dir[d][0];
					dy = p.y + dir[d][1];
					if(check(dx,dy) && !visit[dx][dy]) {
						if(map[dx][dy]==0) {
							visit[dx][dy] = true;
							qu.add(new Pos(dx,dy));
							e--;
						}else if(map[dx][dy]==2) {
							visit[dx][dy] = true;
							qu.add(new Pos(dx,dy));
						}
					}
				}
				if(e==0) return c+1; // 한싸이클 더 돌기전에 리턴하므로 c+1
			}
			c++;
		}
		/*
		 * 공백이 하나라도 남아있을 때 MAX값 리턴
		 * 한싸이클 더 돌고 리턴하므로 c-1
		 */
		return e==0 ? c-1 : Integer.MAX_VALUE; 
	}
	
	static class Pos{
		int x,y;
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "[x=" + x + "," + y + "]";
		}
		
	}
}



Search