연구소2

📍 문제 설명

 

💡 접근

이전 문제와는 다르게 바이러스를 놓을 수 있는 위치가 주어지고 해당 위치에 따른 바이러스 전파 시간을 구하는 문제이다.(조합)

조합을 만들 때 마다 해당 좌표에서 전파시키기 위해 리스트에 담는다.

해당 위치는 거리 기록을 위해 0으로 변경시켜 놓는다.

시작 지점을 표시해놓기 위해 시작 지점을 1의 거리로 초기화 시켜 놓는다.

그리고 상하좌우로 벽이 아니고 거리 기록이 가능한 지점이면 거리를 기록해놓는다.

모든 기록이 끝난 후 거리 기록이 안된 곳(0인 지점)이 있으면 최댓값을 대입하고 멈춘다.

그게 아니라면 거리 중 최댓값(바이러스 전파가 끝나는 시간)을 구한다.

각 조합에 대한 최솟값을 result에 담아두고 결과 출력시에는 result-1로 출력한다.

그리고 result가 최댓값이라면 모든 지점에 대해 전파되는 조합이 없다는 뜻이므로 -1을 출력한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer, cnt, max, min, wall, result = Integer.MAX_VALUE;
    static int[][] board, clone, dis;
    static boolean[] visited;
    static int[] parent = new int[100001];
    static int[] ch,pm, combi;
    static boolean flag = false;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Point> list = new ArrayList<>();
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt(); //연구소의 크기
        m = kb.nextInt(); //바이러스의 개수
        board = new int[n][n];
        //원본 배열 복사
        clone = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = kb.nextInt();
                if(board[i][j] == 2) {
                    list.add(new Point(i, j));
                    board[i][j] = 0;
                }
            }
        }
        visited = new boolean[list.size()];
        //바이러스를 무조건 m개 채우고나서 전파시켜보기
        T.solution(0, 0);
        if(result == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(result - 1);
    }

    private void solution(int L, int s) {
        //조합 뽑았으면 해당 위치에서 바이러스 전파
        if(L == m) {
            Queue<Point> q = new LinkedList<>();

            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    clone[i][j] = board[i][j];
                }
            }
            //거리 기록 배열
            dis = new int[n][n];
            //큐에 해당 위치 넣고 시작 지점 기록
            for(int i = 0; i < list.size(); i++) {
                if(visited[i]) {
                    q.add(list.get(i));
                    dis[list.get(i).x][list.get(i).y] = 1;
                }
            }
            while(!q.isEmpty()) {
                Point cp = q.poll();

                for(int i = 0; i < 4; i++) {
                    int nx = cp.x + dx[i];
                    int ny = cp.y + dy[i];
                    if(nx<0 || ny<0 || nx>=n || ny>=n || clone[nx][ny] != 0 || dis[nx][ny] != 0) continue;

                    //거리 기록 가능한 지점이면 기록하기
                    if(clone[nx][ny] == 0 && dis[nx][ny] == 0) {
                        dis[nx][ny] = dis[cp.x][cp.y] + 1;
                        q.offer(new Point(nx, ny));
                    }
                }
            }
            answer = 0;
            //거리 기록 안된 곳 찾기 & 최댓값 찾기
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //벽이 아닌데 거리기록이 안된 부분이 있으면 해당 조합으로는 전파 불가
                    if (clone[i][j] != 1 && dis[i][j] == 0) {
                        answer = Integer.MAX_VALUE;
                        break;
                    }
                    //모든 바이러스가 퍼지는 시각 구하기
                    if (dis[i][j] > answer) answer = dis[i][j];
                }
            }
            result = Math.min(result, answer);
        }
        else {
            for(int i = s; i < list.size(); i++) {
                if(!visited[i]) {
                    visited[i] = true;
                    solution(L + 1, s + 1);
                    visited[i] = false;
                }
            }
        }
    }

    private static class Point {
        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}