[BOJ] 17141 (연구소2) - Java

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

17141번: 연구소 2

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다.

 

예제 입력 1

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

 

예제 출력 1

5

[풀이]

연구소1 문제보다 조금 상향되고 시간복잡도에서 썰린 문제다.

 

무작정 2중 반복문 돌리면서 빈칸을 찾는다던지, 퍼트릴 바이러스 위치를 찾으면 바로 시간초과뜸.

 

나는 '2'로 입력받은 애들을 '#'으로, 그리고 m개만큼은 '*'로 바꿔서

 

'#' : 바이러스가 배치될 수 있는 자리

 

'*' : 실제 바이러스를 배치해서 퍼트릴 자리

 

로 구분했다.

 

여기서 copy배열을 만든 이유는 BFS를 실행하면서 직접적으로 map의 값을 바꿔주며 최단거리를 갱신하게 되면

 

BFS 탐색조건에 '빈칸인 곳을 찾거나 바이러스가 배치될 수 있는 자리(결국 배치받지 못해 빈칸인 것과 마찬가지)

 

영향을 미치기 때문에 배열을 복사를 해서 값을 갱신하고 바이러스를 퍼트리는 작업을 따로 처리해줬다.

 

나머지는 주석으로 달아놔야징~

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m;
    //실제 map과 복사 배열
    static String[][] map, copy;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int min;
    static int time;
    static Queue<Pair> q;
    //매 탐색마다(빈칸없이 바이러스가 퍼트려진 경우) 시간을 저장하는 리스트
    static List<Integer> answer;
    
    //입력받으면서 바이러스위치를 미리 리스트에 담아주기 위함(시간초과 꺼졍)
    static List<Pair> virusList;
	
    //바이러스를 퍼트리면서 좌표와 퍼트려지는 시간 측정하기 위한 클래스
    static public class Pair {
        int x;
        int y;
        int size;

        Pair(int x, int y, int size) {
            this.x = x;
            this.y = y;
            this.size = size;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        answer = new ArrayList<>();
        map = new String[n][n];
        copy = new String[n][n];
        visited = new boolean[n][n];
        virusList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = st.nextToken();
                //입력받을 때 '2'로 들어오는 애들은 바이러스이므로 리스트에 추가해주면서
                //알아보기 쉽게 '#'으로 바꿔줬다.
                if (map[i][j].equals("2")) {
                    virusList.add(new Pair(i, j, 0));
                    map[i][j] = "#";
                }
            }
        }
		
        //바이러스를 배치하는 완전탐색 함수
        makeVirus(0, 0);

        if (answer.size() == 0) {
            System.out.println(-1);
            System.exit(0);
        }
        System.out.println(Collections.min(answer));
    }
	
    //index : 바이러스 리스트에서의 인덱스
    //count : m개 만큼 배치한 뒤 퍼트리는 함수를 실행할 조건
    public static void makeVirus(int index, int count) {
        min = Integer.MAX_VALUE;
        if (count == m) {
        	//탐색할 때마다 초기화시켜줘야함
            
            visited = new boolean[n][n];
            q = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j].equals("*"))
                        q.offer(new Pair(i, j, 0));
                    else if (map[i][j].equals("1"))
                        map[i][j] = "-";
                    copy[i][j] = map[i][j];
                }
            }

            time = spreadVirus();           //0이 없는 경우의 최소시간
            //print();
            if (isExist()) return;			//빈칸('0')이 하나라도 있으면 탈출하고 다음 케이스로 진행
            //굳이 이렇게 해준 이유는 최소시간만 갖고 완전탐색을 돌리면
            //빈칸이 있는 경우의 최소시간이 더 작게 나올 때 time이 갱신되면서 구분을 할 수가 없기 때문에
            //굳이....리스트를 만들어서 빈칸이 없는 경우만 리스트에 담아줬다.
            answer.add(time);				
            return;
        }
        
        //바이러스 리스트안에 값들을 하나씩 체크하면서 완전탐색
        for (int i = index; i < virusList.size(); i++) {
            int x = virusList.get(i).x;
            int y = virusList.get(i).y;
            map[x][y] = "*";
            makeVirus(i + 1, count + 1);
            map[x][y] = "#";
        }

    }
	
    //바이러스 퍼트리는 함수
    public static int spreadVirus() {
        int tmp = Integer.MIN_VALUE;

        while (!q.isEmpty()) {
            Pair cur = q.poll();
            //바이러스가 배치되고 퍼트리기 시작한 곳은 아직 시간이 0임
            int cx = cur.x;
            int cy = cur.y;
            int cs = cur.size;
            visited[cx][cy] = true;

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if (!visited[nx][ny]) {
                //빈칸인 경우에는 바이러스를 퍼트린다
                //'#'으로 된 곳도 결국 바이러스 배치가 안됐으므로 빈칸으로 간주함
                    if (map[nx][ny].equals("#") || map[nx][ny].equals("0")) {         
                        copy[nx][ny] = String.valueOf(cs + 1);
                        visited[nx][ny] = true;
                        q.offer(new Pair(nx, ny, cs + 1));
                    }else if(map[nx][ny].equals("*")){
                        continue;
                    }
                }
            }
            //nx, ny값이 배열 밖을 벗어날 수도 있기 때문에 현재의 시간값을 tmp에 담아준다.
            //배열 밖을 벗어난 cs+1값을 tmp에 담아버리면 답없어짐
            tmp = Math.max(tmp, cs);
        }
        return tmp;
    }
    
    //0이 있는지 체크
    public static boolean isExist() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (copy[i][j].equals("0"))
                    return true;
            }
        }
        return false;
    }
	
    public static void print(){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(copy[i][j]+" ");
            }
            System.out.println();
        }
    }
}