[백준](Java) 17141 - 연구소 2

문제 링크

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

문제 풀이

연구소3의 풀이에서 몇가지가 수정되었다.

바이러스를 배치하지 않은곳은 사실상 0이라고 생각해야 하는점이 차이점이었다. 그래서
bfs를 돌때 map[i][j]=2 인곳을 0으로 바꿔주며 cnt++를 해주었는데 이렇게 되면 진짜 바이러스를 놓는 곳도 포함이 되버리므로 map[][] = 3을 해줄때 다시 cnt--를 해주었다.

또한 연구소3에서는 zerocnt가 0인경우는 if문을 통해서 바로 0을 출력하게 했지만 이 경우는 바이러스 놓을곳은 4개이지만 실제로 바이러스를 2개만 놓는 경우가 발생하는경우가 있으므로 if문을 제거했다.

코드

import java.util.*;

public class Main {

    static int n;
    static int m;
    static boolean [] viruschk;
    static int res = Integer.MAX_VALUE;
    static int temper =0;
    static boolean minuschk = false;
    static int zerocnt = 0;
    //상 우 하 좌
    static int [] diry = {-1,0,1,0};
    static int [] dirx = {0,1,0,-1};
    static int [][] originMap; //맵 원본
    public static class Node{
        int y;
        int x;
        public Node(int y, int x){
            this.y=y;
            this.x=x;
        }

        public String toString(){
            return "y : "+y+" x : "+x;
        }
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt(); //바이러스를 놓을수 있는 위차
        originMap = new int[n][n];
       int [][] map = new int[n][n];
        List<Node> viruspos = new ArrayList<>();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = sc.nextInt();
                originMap[i][j] = map[i][j];
                if(map[i][j]==2){
                    viruspos.add(new Node(i,j));
                }else if(map[i][j]==0){
                    zerocnt++;
                }
            }
        }
        Node [] pos = new Node[m];
        viruschk = new boolean[viruspos.size()];
        //위치 설정
            dfs(0,0,viruspos,pos,map);
            System.out.println(minuschk ? -1 : res);



    }

    public static void dfs(int idx,int checker, List<Node>viruspos,Node [] pos, int [][]map){

        if(idx==m){
            //bfs돌리기
            bfs(pos,map);
            // -1 이 나온 상태에서 res값이 갱신되지 않았다는것은, 모든 칸에 바이러스를 퍼트리는 경우가 나오지 않았다는 뜻이므로
            //minuschk라는 값을 true로 바꿔둬서 마지막에 -1을 사용할지 res값을 사용할지 체크한다.
            if(temper == -1){
                if(res==Integer.MAX_VALUE){
                    minuschk = true;
                }
            }else{
                //만약에 res값이 -1이 아닌 값으로 바꼈다면, minuschk를 false로바꿔서 마지막에 res가 -1로 되는 것을 막는다.
                res = Math.min(res,temper);
                minuschk = false;
            }
            //temper값 초기화...
            temper=0;
            return;
        }

        for(int i=checker; i<viruspos.size(); i++){
            if(viruschk[i]){
                continue;
            }
            pos[idx] = viruspos.get(i);
            viruschk[i] = true;
            dfs(idx+1,i,viruspos,pos,map);
            viruschk[i] = false;
        }

    }

    public static void bfs(Node [] pos, int [][]map){
        Queue<Node> queue = new LinkedList<>(); //temp 에서 모인 바이러스들을 확신시키는 로직 수
        Queue<Node> temp = new LinkedList<>(); //해당 초동안에 확산된 바이러스들을 담음
        int cnt = zerocnt;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = originMap[i][j];
                if(map[i][j]==2){
                    map[i][j]=0;
                    cnt++;
                }
            }
        }

        for(int i=0; i<pos.length; i++){
            int now_y = pos[i].y;
            int now_x = pos[i].x;
            map[now_y][now_x]=3; //진짜 바이러스
            cnt--;
            temp.add(new Node(now_y,now_x));
        }
        while(!temp.isEmpty()) {
            while(!temp.isEmpty()){
                queue.add(temp.poll());
            }
            boolean timer = false; //이번 초동안에 확산시킨 바이러스가 있다면 ++를 해준다.
            while (!queue.isEmpty()) {
                Node now = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int now_y = now.y + diry[i];
                    int now_x = now.x + dirx[i];
                    if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < n) {
                        if (map[now_y][now_x] == 0) {
                            cnt--;
                            map[now_y][now_x] = 3;
                            timer = true;
                            temp.add(new Node(now_y, now_x));
                        }
                    }
                }
            }//queue.isEmpty()
            if(timer){
                temper++;
            }
            if(cnt==0){
                break;
            }
        }//temp.isEmpty()
        //체크
        temper = cnt !=0 ? -1 : temper;
    }
}