[PS][java][완전탐색][백트래킹+BFS]/[연구소2]

boj-java-17141.java

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

public class Main {
    static int n,m;
    static int[][] map, map2;
    static boolean[][] visit;
    static int ans = 0xFFFFFF;
    static int idx=0;
    static Point[] arr = new Point[11];
    static Point[] selected = new Point[11];
    static boolean[] arrVisited;
    static Queue<Point> q = new LinkedList<>();
    static class Point{
        int r,c;//row column
        Point(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    static int[] dr = {0,0,1,-1};
    static int[] dc = {1,-1,0,0};

    static int bfs(){
        int time = -1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                Point curr = q.poll();
                for(int k=0; k<4; k++){
                    int nr = curr.r + dr[k];
                    int nc = curr.c + dc[k];
                    if(nr<0 || n<=nr || nc <0 || n <=nc) continue;
                    if(map2[nr][nc] == 0 && !visit[nr][nc]){
                        map2[nr][nc] = 2;
                        visit[nr][nc] = true;
                        q.offer(new Point(nr,nc));
                    }
                }
            }
            time++;
        }
        for(int i=0; i< n; i++){
            for(int j=0; j<n;j++){
                if(map2[i][j] == 0){
                    time = 0xFFFFFF;
                }
            }
        }
        return time;
    }
    static void showMap(int[][] map){
        System.out.println("========");
        for(int i=0; i< n; i++){
            for(int j=0; j<n; j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }

    static void recur(int start, int depth){
        if(depth == m){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    map2[i][j] = map[i][j];
                }
            }
            visit = new boolean[n][n];
            for(int i=0; i<m; i++){
                map2[selected[i].r][selected[i].c] = 2;
                visit[selected[i].r][selected[i].c] = true;
                q.offer(new Point(selected[i].r,selected[i].c));
            }
            int t = bfs();
            ans = Math.min(ans,t);
            return;
        }

        for(int i=start; i<idx;i++){
            if(arrVisited[i]) continue;
            arrVisited[i] = true;
            selected[depth] = arr[i];
            recur(i+1,depth+1);
            arrVisited[i] = false;
        }

    }


    public static void main(String[] args) throws IOException {
        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 int[n][n];
        map2 = new int[n][n];
        for(int i=0; i< n; i++){
            String[] line = br.readLine().split(" ");
            for(int j=0; j<n; j++){
                map[i][j] = line[j].charAt(0)-'0';
                if(map[i][j] == 2){
                    arr[idx++] = new Point(i,j);
                    map[i][j] = 0;
                }
            }
        }
        arrVisited = new boolean[idx];
        recur(0,0);
        System.out.println(ans == 0xFFFFFF ? -1 : ans);
    }
}