알고리즘27 :: BOJ_17142_연구소3

package backjun모음;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/*
이 문제는 4번을 풀었다.
처음엔 내 맘대로
두번쨰는 조금 생각해서
세번쨰는 걍 생각 좀 더 해서
네번쨰는 블로그 보고 ;; 
 
for(int i=nn; i<al.size(); i++) {//조합을 사용한다. 바이러스 개수만큼 돈다. 
 
                if(visit[i] == 0) {//이동하는 조건은 방문 체크를 해서 반만 본다.                  
                    visit[i] = 1;
                    go(i+1, cnt+1); //cnt는 바이러스 체크 하는건데 
                    visit[i] = 0;
 
}
조합을 이런식으로 쓰는게 조금 어색했다. 
아무튼 순열 조합을 index로 넘겨주는 연습을 다시 봐야할 것 같다. 
 
그리고 바이러스 개수를 고르는것이 
방문 체크로 고르는것도 신선했다. 시간이 되면 다시 풀어보는것도 잉여시간이나.
 
특히 dist 배열을 둬서 증가하는 값에 따라 마지막 결과 출력을 이어가는것은 평소에 잘 안쓰던 나에게 반성하게 했다.
훨~~~씬 편했다. 맵을 따로 안만들어 줘도 되서...
 
그외는 일반적인 BFS 를 따라갔다. 
 
힘든 문제니까 다시 풀어봐야지 
 
*/
public class backjun_연구소3 {
 
    private static int n;
    private static int virus;
    private static int[][] map;
    private static int[][] dist;
    private static int comparison;
    private static int[] visit;
    private static int ans = Integer.MAX_VALUE;
    private static ArrayList<int[]> al;
    private static Queue<int[]> Q;
 
    private static int[] dx = {-1,1,0,0};
    private static int[] dy = {0,0,-1,1};
    private static void BFS() {
        //4방탐색을 진행한다. 
        int bb = 0, time = 0;
        while(!Q.isEmpty()) {
            int[] gg =  Q.remove();
 
            for(int i=0; i<4; i++) {
                int ddx = gg[0]+dx[i];
                int ddy = gg[1]+dy[i];
 
                if(ddx<0 || ddx>=n || ddy<0 || ddy>=n) continue;
 
                if(map[ddx][ddy] !=1 && dist[ddx][ddy] ==-1) {
                    //dist 의 값을 1 증가시킨다. 
                    dist[ddx][ddy] = dist[gg[0]][gg[1]]+1;
                    Q.add(new int[] {ddx,ddy});
                    if(map[ddx][ddy] == 0) {
                        bb+=1;//빈칸이라면 개수를 체크하고 
                        //time 에 dist를 업데이트 
                        time = dist[ddx][ddy];
                    }
                }
 
                //맵에서 벽이 아니고, dist의 값이 -1 이라면 한번도 간적이 없으므로 
 
            }
        }
        //큐에서 다 꺼내는 시점에서 감염된곳과 아까 빈칸의 개수가 맞는지 체크 
        //그리고 ans 를 둬서 time과 비교해서 ans 가 더 크면 time 을 업데이트 
      
 
        if(bb==comparison && ans>time) {
 
                //ans 출력 
 
                ans = time;
 
        }
 
    }
    //재귀1 
    private static void go(int nn, int cnt) {
        if(virus == cnt) {
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    dist[i][j] = -1;//바이러스 개수가 맞다면, dist 초기화
 
                }
            }
 
            //바이러스 개수만큼 반복문을 돌면서 바이러스 좌표를 저장해둔 자료구를 큐에 담는다. 
            for(int i=0; i<al.size(); i++) {
                if(visit[i] == 1) {
                    Q.add(new int[] {al.get(i)[0], al.get(i)[1]});
                    //이때 시작하는 바이러스 위치 의 dist의 값은 0이다. 
                    dist[al.get(i)[0]][al.get(i)[1]] = 0;   
                }
            }
 
            //bfs2
            BFS();
 
        }else {
            for(int i=nn; i<al.size(); i++) {//조합을 사용한다. 바이러스 개수만큼 돈다. 
 
                if(visit[i] == 0) {//이동하는 조건은 방문 체크를 해서 반만 본다.
 
                    visit[i] = 1;
                    go(i+1, cnt+1);
                    visit[i] = 0;
 
                }
            }
 
        }
    }
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        //입력 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력시 벽을 세운다. 
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        virus = Integer.parseInt(st.nextToken());
        map = new int[n][n];
        comparison = 0;
        visit = new int[10];
        dist = new int[n][n];
        Q = new LinkedList<int[]>();
 
        al = new ArrayList<>();
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2) {
                    al.add(new int[] {i,j});
                }
                if(map[i][j] == 0)
                    comparison+=1;
            }
        }
 
        //2인 경우는 저장할 곳에 넣는다. ->ok
 
        //빈칸은 하나씩 증가시킨다. ->ok
 
        //재귀함수 호출시킨다. 
 
        go(0,0);
        if(ans == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
 
}