백준 17141번 연구소 2 (JAVA)

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

17141번: 연구소 2

 

저는 해당 문제를 조합과 BFS를 통해서 문제를 해결하였습니다.

choice를 통해서 조합으로 2를 m개만큼 선택하고 q에 넣어서 BFS를 사용하였습니다.

check를 통해 벽을 제외한 모든 곳을 방문하였는지 체크하였습니다. 이때 바이러스가 방문한 곳을 2로 변경하여 처리하는 것이 아니라 map과 visited 배열을 통해 확인하였습니다. 

해당 좌표가 map에서 1이 아니고 (벽이 아니고) 방문한 적이 없다면 모든 곳이 바이러스가 된 것이 아니라고 판단하였습니다.

 

 

package BOJ.BFS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_17141 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int[][] map = new int[n][n];
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 0 ; j < n ; j++){
                map[i][j] = stoi.apply(st.nextToken());
            }
        }
        System.out.println(cal(map,n,m));
    }
    private static final int[] dy = {-1,0,1,0};
    private static final int[] dx = {0,1,0,-1};
    private static int cal(int[][] map, int n , int m){
        List<int[]> list = new ArrayList<>();
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                if(map[i][j] == 2){
                    list.add(new int[] {i,j});
                }
            }
        }
        int[] virus = new int[m];
        int result = choice(0, 0, list, m, virus,map,n);
        return result;
    }

    private static int choice(int depth, int start,List<int[]> list, int m,int[] virus,int[][]map,int n) {
        if(depth == m){
            boolean[][] visited = new boolean[n][n];
            Queue<int[]> q = new LinkedList<>();
            for(int i = 0 ; i < m ; i++){
                int[] location = list.get(virus[i]);
                q.offer(location);
                visited[location[0]][location[1]] = true;
            }
            return bfs(q,map,n,visited);
        }
        int result = -1;
        for(int i = start ; i < list.size(); i++){
            virus[depth] = i;
            int temp = choice(depth+1,i+1,list,m,virus,map,n);
            if(temp != -1){
                if(result == -1){
                    result = temp;
                }else{
                    result = Math.min(result,temp);
                }
            }
        }
        return result;
    }

    private static int bfs(Queue<int[]> q,int[][] map, int n,boolean[][] visited) {
        int time = -1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size ; s++){
                int[] now = q.poll();
                for(int i = 0 ; i < 4 ; i++){
                    int ny = now[0] + dy[i];
                    int nx = now[1] + dx[i];
                    if(ny >= 0 && ny < n && nx >= 0 && nx < n && !visited[ny][nx] && map[ny][nx] != 1){
                        q.offer(new int[] {ny,nx});
                        visited[ny][nx] = true;
                    }
                }
            }
            time++;
        }
        if(check(map,n,visited)){
            return time;
        }else{
            return -1;
        }
    }
    private static boolean check(int[][] map,int n,boolean[][] visited){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                if(!visited[i][j] && map[i][j] == 0){
                    return false;
                }
            }
        }
        return true;
    }
}