[BOJ] 연구소 3 - 17142 (Java)

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

17142번: 연구소 3

[풀이]

연구소2 문제랑 다를바가 없어보이지만 이해하는데만 시간다쓴 문제.

 

연구소 2 : 바이러스가 배치될 수 있는 좌표에 실제로 배치를 하고 퍼트린다.

그말인 즉슨, 배치가 되지 않은 좌표는 빈칸이므로 똑같이 BFS를 실행하면 된다는 뜻!

 

연구소 3 : 바이러스는 활성화, 비활성화 상태가 있고 M개만큼 활성화를 시킨 뒤에 퍼트린다.

비활성화가 되었다고 해서 빈칸인 것이 아니고, 똑같은 바이러스이다. 그러니까 지도 전체에서 빈칸이 없기만 하면 됨

 

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

public class Main {
    static int n, m, time, zeroCnt, zeroTmp;	//빈칸(0)의 갯수를 미리 세어놓기 위한 변수
    static String[][] map;
    static String[][] copy;
    static boolean[][] visited;
    static List<Pair> virusList;		//시간복잡도를 줄이기 위해 바이러스의 좌표를 넣어준다
    static int max;
    static Queue<Pair> q;
    static List<Integer> timeList = new ArrayList<>();	//바이러스를 퍼트린 케이스마다의 걸린 시간 리스트
    static public class Pair{
        int x;
        int y;
        int dist;
        Pair(int x, int y, int dist){
            super();
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    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());               //바이러스의 개수

        map = new String[n][n];
        copy = new String[n][n];
        //visited = new boolean[n][n];
        virusList = new ArrayList<>();
        zeroCnt = 0;
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<n;j++){
                map[i][j] = st.nextToken();
                if(map[i][j].equals("2")){
                    virusList.add(new Pair(i, j, 0));           //2로 표시된 부분 : 바이러스
                    map[i][j] = "#";
                }
                if(map[i][j].equals("0")) zeroCnt++;			//빈칸
            }
        }

        makeVirus(0, 0);
        if(timeList.size() == 0){				//바이러스를 아무리 배치해도 걸린 시간이 리스트안에 없으면 -1
            System.out.println("-1");
            System.exit(0);
        }

        System.out.println(Collections.min(timeList));
    }


    public static void makeVirus(int index, int depth){
        if(depth == 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];			//원래 map 배열에서 값을 비교하고, 매 케이스마다
                }									//복제한 copy배열에 값을 기록하면서 진행한다
            }
            if(zeroCnt == 0){						//빈칸이 존재하지 않은 상태로 입력되었으면
                System.out.println("0");			//자동 0 출력하고 종료
                System.exit(0);	
            }
            spreadVirus();
            if(zeroTmp > 0) return;           // 0이 존재하면 벗어나기(바이러스를 퍼트렸음에도 빈칸이 있다면 고려할필요가 없음)
            else{
                timeList.add(max);			//빈칸이 없다면 걸린시간을 리스트에 담아준다
            }
            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, depth + 1);		   //비활성화 바이러스 : #
            map[x][y] = "#";
        }

    }

    public static void spreadVirus(){
        max = Integer.MIN_VALUE;
        zeroTmp = zeroCnt;			//매 케이스마다 빈칸의 갯수를 사용해야되니까 tmp하나만들기
        while(!q.isEmpty() && zeroTmp > 0){	
            Pair cur = q.poll();
            int cx = cur.x;
            int cy = cur.y;
            int cd = cur.dist;
            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("0")) {		//빈칸이면 그냥 바이러스퍼트리기
                        visited[nx][ny] = true;
                        copy[nx][ny] = String.valueOf(cd + 1);		//복제한 배열에 그 값을 기록하자
                        q.offer(new Pair(nx, ny, cd + 1));
                        zeroTmp--;						//빈칸 갯수 하나 줄여주고
                    } else if (map[nx][ny].equals("*")) continue;	//활성화 바이러스면 건들지말고 넘어가기(어차피 다음번에 체크함)
                    else if (map[nx][ny].equals("#")) {			//비활성화 바이러스라면 
                        visited[nx][ny] = true;
                        q.offer(new Pair(nx, ny, cd+1));		//값을 기록하진 않는다
                    }
                }
            }
            max = Math.max(max, cd+1);
        }

    }

}

 

반례중에

 

[입력]

5 1
0 2 2 2 2
0 1 2 2 2
0 1 2 2 2
0 1 2 2 2
0 1 2 2 1

 

[출력]

5

 

가 나와야 하는데, 돌려보면 6이 나오는 경우가 있다.

 

제일 빠른 루트는 0행 1열에 있는 2에서 왼쪽 0을 타고 쭉 내려가는것인데,

 

그림으로 나타내면

 

1 * # # #    (# : 비활성 바이러스)
2 - # # # 
3 - # # # 
4 - # # # 
5 - # # - 

 

이렇게 나와야한다.

 

단순히 2차원 copy배열에 BFS를 진행할때마다 그 값을 기록하면서 진행하게 되면

 

1 * 1 2 3      (비활성된 바이러스들이 활성화되면서 얘네들이 탐색을 다해야 큐가 비워지면서 BFS가 종료됨)
2 - 2 3 4
3 - 3 4 5 
4 - 4 5 6 
5 - 5 6 - 

 

이런 식으로 된다.

 

제일 빠른 바이러스위치(0행 2열)에서 출발해서 왼쪽 0을 만나 큐에 담고(1)

 

오른쪽에 비활성된 바이러스를 만나면서 큐에 담고(2)

 

아래로 이동하면서 비활성된 바이러스를 만나면서 큐에담는다(3)

 

왼쪽으로 가는길이 가장 빠른 루트라 해도 큐는 선입선출이기 때문에 먼저 들어온 비활성 -> 활성화 된 아이들이 빠져나가야만 빠른 루트로 갈 수있다.