[BOJ] 17142 연구소3 - Java

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

[풀이]

1. 바이러스 중 활성화 시킬 M개의 조합을 dfs를 통해 구한다.

void dfs(int index, int count) , VirusVisit boolean 배열을 이용해서 조합을 구한다.

static boolean[] visit = new boolean[N];
static ArrayList<Integer> Active = new ArrayList<>();

//N개 고르기
dfs(0,0);

static void dfs(int index,int count) {
		if(count>=N) {
			System.out.println(Active); //N개 조합 완성
			return;
		}
		for(int i=index;i<N;i++) {
			if(!visit[i]) {
				visit[i] = true;
				Active.add(i);
				dfs(i+1,count+1);
				visit[i] = false;
				Active.remove(Active.size()-1);
			}
		}
	}

2. 각 활성 바이러스 조합마다 퍼뜨리기 시작한다. spread 함수 -> BFS를 이용

(왜? -> 빈칸이 모두 채워지는 최소 날짜를 구할 것이므로 최단 거리를 빨리 찾을 수 있는 bfs를 이용한다.)

  2-1. 제일 처음에 Queue에 활성화된 바이러스(위에서 구한 조합) 들을 넣어두고 큐가 빌 떄까지 돌린다.

  2-2. BFS에서는 큐에 넣는 자료에 count를 내장하여 돌리면 손쉽게 몇 번 돌렸는지를 구할 수 있다. 그래서 Point에 count변수를 두고, 1로 초기화 해줬다.

  (0이 아니라, 1로 초기화 한 이유는 맨 처음 활성화된 바이러스들이 빈칸을 모두 채웠을 때 1초임을 생각해보면 이유를 알 수 있다.)

  2-3. 맨 처음에 입력 받을 때 빈칸의 수를 세어놨다. (blankNum)

total 이라는 변수로 빈칸을 채워가는 수를 셀 것인데, total>=blankNum이면 다 채웠다는 것이고 이때 이전까지 갔던 Point들 중 count가 가장 높은 애를 리턴한다. (얘가 빈칸을 다 채우는데 걸린 시간이다.)

 

** 주의

time은 이전까지 갔던 Point들 중 가장 count가 높은 애이다. Math.max를 통해 구한다.

그런데, 새로 들어왔을 때 이전 로직에 의해 빈칸이 이미 다 채워져 있다면, 새로 들어온 애의 count로 time을 갱신하면 안된다.

(생각해보자. 4초 때 빈칸이 다 채워졌다. 이때 방문한 Point를 A라고 해보자,  근데 현재 코드는 빈칸이 다 채워짐을 A다음 Point(B라고 해보자) 를 방문할 때야 알 수 있다. 만약 B가 4초라면 다행히겠지만, 간발의 차이로 5초일수도 있다. 

이때 B의 count를 리턴한다면 올바르지 않은 답이 나온다. 때문에 time이라는 변수를 두고, 빈칸을 먼저 체크한다음, 빈칸을 다 채우지 않고 다음 칸을 향해서 가는 애임이 밝혀진다면 time을 갱신한다.)

    int time = -1;

    while(!queue.isEmpty()) {
        Point nowVirus = queue.poll();
        if(total>=blankNum) { //먼저 만족했는지 확인하고
            return time;
        }
        time = Math.max(time,nowVirus.count); //time 갱신하기

        ...
    }

3. 또 주의 - 나는 처음에 빈칸일 때만 바이러스가 확장하는 것으로 했는데, 생각해보니 비활성 바이러스여도 칸을 방문해서 확산되어야 한다. (근데 빈칸 갯수는 갱신하지 않아야 함)

그래서 확산 시 빈칸, 비활성 바이러스의 경우를 나누었다.

 

[코드]

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

/*
사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
*/
class Boj17142_연구소3 {
	static StringTokenizer st;
	static int N,M;
	static int[][] Map;
	static ArrayList<Point> Blank = new ArrayList<>();
	static ArrayList<Point> Virus = new ArrayList<>();
	static boolean[] VirusVisit;
	static ArrayList<Point> ActiveVirus = new ArrayList<>();
	static int blankNum = 0;
	static int[][] visit;
	static int[] dRow = {-1,1,0,0};
	static int[] dCol = {0,0,-1,1};
	static boolean flag = false;
	static int answer = Integer.MAX_VALUE;
	
	public static void main(String args[]) throws Exception {
		
		System.setIn(new FileInputStream("src/main/java/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		Map = new int[N+1][N+1];
		
		for(int i=1;i<N+1;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<N+1;j++) {
				Map[i][j] = Integer.parseInt(st.nextToken());
				if(Map[i][j] == 0) {//빈칸
					Blank.add(new Point(i,j));
				}
				else if(Map[i][j] == 2) { //바이러스
					Virus.add(new Point(i,j));
				}
			}
		}
		blankNum = Blank.size();
		//System.out.println(blankNum);
		if(blankNum==0) {
			System.out.println(0);
			System.exit(0);
		}
		
		//start
		VirusVisit = new boolean[Virus.size()];
		//M개의 바이러스 고르기
		dfs(0,0);
		
		if(!flag) {
			System.out.println(-1);
		}
		else {
			System.out.println(answer);
		}
	}
	
	static void dfs(int index,int count) {
		//System.out.println(ActiveVirus);
		if(count>=M) {
			//spread
			int sp = spread();
			if(sp!=-100) {
				//System.out.println("갱신 : "+sp);
				answer = Math.min(answer, sp);
				flag = true;
			}
			return;
		}
		for(int i=index;i<Virus.size();i++) {
			if(!VirusVisit[i]) {
				VirusVisit[i] = true;
				ActiveVirus.add(Virus.get(i));
				dfs(i+1,count+1);
				VirusVisit[i] = false;
				ActiveVirus.remove(ActiveVirus.size()-1);
			}
		}
	}
	
	static int spread() {
		//visit 방문처리
		int total = 0;
		
		visit = new int[N+1][N+1]; //각 조합마다 따로 쓰여야 함, 원본 Map은 건드리면 안됨. (다른곳에서도 써야함)
		
		for(int i=1;i<N+1;i++) { //visit 초기화
			for(int j=1;j<N+1;j++) {
				int tmp = Map[i][j];
				if(tmp==2) {
					tmp = -99; //비활성 바이러스
				}
				visit[i][j] = tmp;
			}
		}
		for(Point now:ActiveVirus) {
			visit[now.row][now.col] = 99; //활성바이러스
		}

		int time = -1;
		Queue<Point> queue = new LinkedList<>();
		for(Point active:ActiveVirus){
			queue.add(new Point(active.row,active.col,1)); //count 1로 초기화
		}

		while(!queue.isEmpty()) {
			Point nowVirus = queue.poll();
			if(total>=blankNum) { //먼저 만족했는지 확인하고
				return time;
			}
			time = Math.max(time,nowVirus.count); //time 갱신하기

			for(int i=0;i<4;i++) {
				int newRow = nowVirus.row + dRow[i];
				int newCol = nowVirus.col + dCol[i];
				if(0<newRow && newRow<=N && 0<newCol && newCol<=N) {
					if(visit[newRow][newCol]==0) { //빈칸이라면
						visit[newRow][newCol] = visit[nowVirus.row][nowVirus.col]+1; //빈칸 들름
						total++;
						queue.add(new Point(newRow,newCol,nowVirus.count+1));
					}
					else if(visit[newRow][newCol]==-99) { //비활성바이러스라면
						visit[newRow][newCol] = 99; //빈칸 들름
						queue.add(new Point(newRow,newCol,nowVirus.count+1)); //비활성바이러스의 경우 큐에 추가
					}
				}
			}
		}
		return -100;
	}
	static void printMap() {
		System.out.println("=========");
		for(int i=1;i<N+1;i++) {
			for(int j=1;j<N+1;j++) {
				System.out.print(visit[i][j]+" ");
			}
			System.out.println();
		}
	}
	static class Point{
		int row;
		int col;
		int count;
		
		@Override
		public String toString() {
			return "Point [row=" + row + ", col=" + col + ", count=" + count + "]";
		}

		public Point(int row, int col, int count) {
			super();
			this.row = row;
			this.col = col;
			this.count = count;
		}

		public Point(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}
		
	}
	
}

[느낀점]

소요시간 : 3h쯤..?

아니 분명 다 풀었는데.. 답이 요상하게 나오는 것때문에 애를 먹었다.

BFS를 너무 오랜만에 풀어서 그런가,, 앞으로는 변수를 갱신하는 타이밍! 을 잘 생각하자