[JAVA] BOJ 백준 17142 연구소3

전체 코드

import java.util.*;
import java.io.*;
class Virus{
	public int x;
	public int y;
	Virus(int x, int y){
		this.x = x; this.y = y;
	}
}
public class Main {
	static int N;
	static int M;
	static int[][] lab;
	static int result;
	static ArrayList<Virus> v;
	static ArrayDeque<Virus> energy;
  public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        
        N= Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        lab = new int[N][N];
        v = new ArrayList<>();
        energy = new ArrayDeque<>();
        for(int i=0; i<N; i++) {
        	st = new StringTokenizer(bf.readLine(), " ");
        	for(int j=0; j<N; j++) {
        		lab[i][j] = Integer.parseInt(st.nextToken());
        		if(lab[i][j] == 2) v.add(new Virus(i, j));
        	}
        }
        result = Integer.MAX_VALUE;
        dfs(0, 0);
        if(result == Integer.MAX_VALUE -1) result = -1;
        sb.append(result).append("\\n");
        System.out.println(sb.toString());
        
    }
    
    static void dfs(int count, int x) {
    	if(count == M) {
    		spread();
    		return;
    	}
    	for(int i=x; i<v.size(); i++) {
    		Virus vr = v.get(i);
    		if(lab[vr.x][vr.y] == 3) continue;
    		lab[vr.x][vr.y] = 3;
    		dfs(count+1, i);
    		lab[vr.x][vr.y] = 2;
    	}
    	
    }
    static void spread() {
    	int[] dx = {0, 0, -1, 1};
    	int[] dy = {1, -1, 0, 0};
    	int[][] visited = new int[N][N];
    	int nx, ny;
    	for(int i=0; i<N; i++)
    		for(int j=0; j<N; j++) 
    			if(lab[i][j] == 3) {
    				energy.add(new Virus(i, j));
    				visited[i][j] = 1;
    	}
    	while(!energy.isEmpty()) {
    		Virus vr = energy.poll();
    		for(int d = 0; d<4; d++) {
    			nx = vr.x + dx[d];
    			ny = vr.y + dy[d];
    			if(nx<0 || ny<0 || nx >= N || ny >= N || visited[nx][ny] !=0) continue;
    			if(lab[nx][ny] == 1) continue;
    			else {visited[nx][ny] = visited[vr.x][vr.y] + 1;
    			energy.add(new Virus(nx, ny));}

    		}	
    	}
    	int max = 1;
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<N; j++) {
    			if(lab[i][j] != 0) continue;
	    		if(visited[i][j] == 0) max = Integer.MAX_VALUE;
	    		else if(visited[i][j] > max) max = visited[i][j];
    			
    		}
    	}
    	if(result > max - 1) result = max - 1;	
    }
}

한 줄 씩 살펴보자!

class Virus{
	public int x;
	public int y;
	Virus(int x, int y){
		this.x = x; this.y = y;
	}
}

바이러스의 위치를 저장하기 위해 virus 클래스를 생성하였다. 하지만 int[] 로 대체 가능하다!

static int N;
static int M;
static int[][] lab;
static int result;
static ArrayList<Virus> v;
static ArrayDeque<Virus> energy;

N, M, lab은 주어진 연구소 정보들을 저장하는 값이다.

result에 결과값을 갱신하며 넣어준다.

v는 모든 virus를 넣어준다. energy에는 활성화된 virus를 넣어준다.

lab = new int[N][N];
  v = new ArrayList<>();
  energy = new ArrayDeque<>();
  for(int i=0; i<N; i++) {
  	st = new StringTokenizer(bf.readLine(), " ");
  	for(int j=0; j<N; j++) {
  		lab[i][j] = Integer.parseInt(st.nextToken());
  		if(lab[i][j] == 2) v.add(new Virus(i, j));
  	}
  }
  result = Integer.MAX_VALUE;
  dfs(0, 0);
  if(result == Integer.MAX_VALUE -1) result = -1;
  sb.append(result).append("\\n");
  System.out.println(sb.toString());

for문을 통해 입력받은 값들을 저장한다.

result 변수는 모든 칸에 바이러스를 퍼트리는 최소값이 될것이기 때문에 Max로 설정해준다.

dfs()를 호출한다.

결과값이 max-1인 경우는 모든 칸에 바이러스를 퍼트리는 것이 불가능 하다는 뜻이므로 -1로 세팅한다.

결과값을 출력해준다.

static void dfs(int count, int x) {
	if(count == M) {
		spread();
		return;
	}
	for(int i=x; i<v.size(); i++) {
		Virus vr = v.get(i);
		if(lab[vr.x][vr.y] == 3) continue;
		lab[vr.x][vr.y] = 3;
		dfs(count+1, i);
		lab[vr.x][vr.y] = 2;
	}
	
}

dfs함수를 통해 M개의 활성 바이러스를 정한다.

현재 2로 세팅되어있는 바이러스를 3(활성 상태)로 변경하고 M개를 모두 활성으로 바꾸면 spread함수를 호출하여 초를 계산해준다.

static void spread() {
	int[] dx = {0, 0, -1, 1};
	int[] dy = {1, -1, 0, 0};
	int[][] visited = new int[N][N];
	int nx, ny;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++) 
			if(lab[i][j] == 3) {
				energy.add(new Virus(i, j));
				visited[i][j] = 1;
	}

visited 배열을 통해 이미 조사한 곳은 제외하며 조사한다.

nx, ny를 통해 다음 이동할 곳을 조사한다.

이중 for문을 통해 바이러스의 위치를 찾아 활성화 바이러스에 넣어준다.

이 위치에서 조사를 시작하기 위해 1로 바꾸어준다.

while(!energy.isEmpty()) {
		Virus vr = energy.poll();
		for(int d = 0; d<4; d++) {
			nx = vr.x + dx[d];
			ny = vr.y + dy[d];
			if(nx<0 || ny<0 || nx >= N || ny >= N || visited[nx][ny] !=0) continue;
			if(lab[nx][ny] == 1) continue;
			else {visited[nx][ny] = visited[vr.x][vr.y] + 1;
			energy.add(new Virus(nx, ny));}

		}
		
	}

활성화 바이러스를 하나씩 꺼내서 4방향으로 조사를 해준다. 이때 격자를 벗어나지 않고 방문처리 되지 않았고 벽이 아니라면 visited를 현재 위치보다 1크게 바꾸어준다.(위치에 시간을 표시하기 위함)

그리고 energy에 넣어 다시 사방 탐색을 해준다.

int max = 1;
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<N; j++) {
    			if(lab[i][j] != 0) continue;
	    		if(visited[i][j] == 0) max = Integer.MAX_VALUE;
	    		else if(visited[i][j] > max) max = visited[i][j];
    			
    		}
    	}
    	if(result > max - 1) result = max - 1;	
    }
}

visited에 저장된 초를 탐색한다. 이때 visited가 0인 경우는 방문할 수 없는 경우(즉, 방문이 불가능한 곳)이므로 최대값을 max로 준다.

처음 바이러스의 위치에 1을 넣어준 채로 시작했기 때문에 결과값을 -1해주어 보정한다.