[백준][BFS/DFS][Java] 17141. 연구소 3 (Feat. BFS를 조합마다 돌리지 않기)

문제 링크 : https://www.acmicpc.net/problem/17142

문제 풀이 시간 : 1시간 10분

 

 

처음에는 그냥 '바이러스 조합 고르고, 그때마다 BFS 돌리면 되겠지' 라고 생각했다.

근데 가만히 보니까 이 방식은 뭔가 계속 같은 계산을 반복하는 느낌이 들었다.
어차피 바이러스 후보 위치는 정해져 있는데, 조합만 바뀔 뿐인데 매번 BFS를 새로 돌리는 게 좀 비효율적이라고 생각했다.

 

그래서 각 바이러스에서 모든 칸까지 걸리는 시간을 미리 구해두고, 조합을 뽑을 때는 그 값을 가져다 쓰는 방식으로 풀어보았다.!! 

 

• 바이러스 후보마다 BFS를 한 번씩만 돌린다.
• 각 칸까지 걸리는 시간을 전부 저장한다.
• 이후 M개 조합을 고른다.
• 빈 칸마다 “선택된 바이러스들 중 가장 빨리 도달하는 시간”을 본다.
• 그중 가장 큰 값을 해당 조합의 시간으로 본다.

즉, BFS는 미리 끝내고, 조합에서는 계산만 하는 것이다.

 

times[i][j][k]

• (i, j) : 좌표
• k : k번째 바이러스

즉, times[i][j][k] 는 k번 바이러스가 (i, j) 칸까지 가는 시간을 의미한다.

---

1. 바이러스마다 BFS를 한 번씩 돌리기

제일 먼저, 모든 바이러스 후보에 대해 BFS를 돌리자 ! 해당 바이러스가 활성화 되었을때 모든 칸에 대해 바이러스가 퍼질 시간을 저장하는것이다.

public static void bfs(){
    Queue<Virus> q = new LinkedList<>();
    for(int i = 0; i < virusList.size(); i++){
        Point p = virusList.get(i);
        q.add(new Virus(i, p.i, p.j, 0));
        times[p.i][p.j][i] = 0;
    }

    while(!q.isEmpty()){
        Virus v = q.poll();

        for(int i = 0; i < 4; i++){
            int ni = v.i + dx[i];
            int nj = v.j + dy[i];

            if(ni < 0 || ni >= N || nj < 0 || nj >= N)
                continue;

            if(arr[ni][nj] == 1)
                continue;

            if(times[ni][nj][v.num] != -1)
                continue;

            times[ni][nj][v.num] = v.cnt+1;
            q.add(new Virus(v.num, ni, nj, v.cnt+1));
        }
    }
}

여기서 포인트는 큐에 바이러스를 하나씩 따로 넣되, v.num을 같이 들고 다니면서 “지금 BFS가 몇 번째 바이러스 기준인지”를 구분했다.

 

2. 조합은 DFS로 고르기

BFS를 다 구해놨으니까, 그 다음에는 활성화할 바이러스 M개만 고르면 된다.

public static void dfs(int[] virus, int depth, int index){
        if(depth > M) return;

        if(depth == M){
            int ans = findMin(virus);

            if(ans != -1){
                result = Math.min(result, ans);
            }
            return;
        }

        for(int i = index; i < virusList.size(); i++){
            virus[depth] = i;
            dfs(virus, depth+1, i+1);
        }
    }

이 부분은 일반적인 조합 DFS다.

---

3. 실제 시간 계산은 따로 하기

조합이 하나 완성되면, 그 조합이 모든 빈 칸을 얼마나 빨리 채울 수 있는지 계산해야 한다.

public static int findMin(int[] virus){
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(arr[i][j] != 0) continue;

            int min = Integer.MAX_VALUE;
            for(int v : virus){
                if(times[i][j][v] != -1){
                    min = Math.min(times[i][j][v], min);
                }
            }

            if(min == Integer.MAX_VALUE) return -1;
            max = Math.max(max, min);
        }

    }

    return max;
}

 

 

빈 칸 하나를 기준으로 보면, 선택된 바이러스들 중 누가 가장 빨리 도착하는지가 중요하다. 그래서 각 빈 칸마다 최소 시간을 구한다.

전체 기준으로 보면, 모든 빈 칸이 다 감염되어야 하니까 그 최소 시간들 중 가장 큰 값을 봐야 한다.

• 칸 기준: 최소
• 전체 기준: 최대

---

구현하면서 신경 쓴 부분

1. 빈 칸이 하나도 없는 경우

이건 바로 0을 출력해야 한다.

if(empty == 0) {
    System.out.print(0);
    return;
}

2. 도달할 수 없는 빈 칸이 있는 경우

선택한 바이러스 조합으로 어떤 빈 칸에도 도달할 수 없다면 실패다.

if(min == Integer.MAX_VALUE) return -1;

 

---

BFS 문제라고 해서 무조건 BFS를 반복하는 쪽으로 갈 필요는 없다는 점이다.
같은 계산이 반복되는 게 보이면, 그걸 줄이는 쪽으로 한 번 더 생각해보는 게 확실히 중요한 것 같다.

 

코드 풀이

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

public class Main{
    static int N, M;
    static int[][] arr;
    static int empty;
    static List<Point> virusList;
    static int[][][] times;
    static int result = Integer.MAX_VALUE;
    static int[] dx = {-1, 1, 0, 0 };
    static int[] dy = {0, 0, -1, 1};
    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());

        virusList = new ArrayList<>();
        arr = new int[N][N];

        for(int i = 0; i < N; i++){
            st =  new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());

                if(arr[i][j] == 0){
                    empty++;
                }else if(arr[i][j] == 2){
                    virusList.add(new Point(i, j));
                }
            }
        }

        if(empty == 0) {
            System.out.print(0);
            return;
        }

        times = new int[N][N][virusList.size()];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(int k = 0; k < virusList.size();k++){
                    times[i][j][k] = -1;
                }

            }
        }

        bfs();


        dfs(new int[M], 0, 0);

        System.out.print(result == Integer.MAX_VALUE ? -1 : result);
    }

    public static void dfs(int[] virus, int depth, int index){
        if(depth > M) return;

        if(depth == M){
            int ans = findMin(virus);

            if(ans != -1){
                result = Math.min(result, ans);
            }
            return;
        }

        for(int i = index; i < virusList.size(); i++){
            virus[depth] = i;
            dfs(virus, depth+1, i+1);
        }
    }

    public static int findMin(int[] virus){
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(arr[i][j] != 0) continue;

                int min = Integer.MAX_VALUE;
                for(int v : virus){
                    if(times[i][j][v] != -1){
                        min = Math.min(times[i][j][v], min);
                    }
                }

                if(min == Integer.MAX_VALUE) return -1;
                max = Math.max(max, min);
            }

        }

        return max;
    }

    public static void bfs(){
        Queue<Virus> q = new LinkedList<>();
        for(int i = 0; i < virusList.size(); i++){
            Point p = virusList.get(i);
            q.add(new Virus(i, p.i, p.j, 0));
            times[p.i][p.j][i] = 0;
        }

        while(!q.isEmpty()){
            Virus v = q.poll();

            for(int i = 0; i < 4; i++){
                int ni = v.i + dx[i];
                int nj = v.j + dy[i];

                if(ni < 0 || ni >= N || nj < 0 || nj >= N)
                    continue;

                if(arr[ni][nj] == 1)
                    continue;

                if(times[ni][nj][v.num] != -1)
                    continue;

                times[ni][nj][v.num] = v.cnt+1;
                q.add(new Virus(v.num, ni, nj, v.cnt+1));
            }
        }
    }

    public static class Virus{
        int num, i, j, cnt;
        public Virus(int num, int i, int j, int cnt){
            this.num = num;
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
    }

    public static class Point{
        int i, j;
        public Point(int i, int j){
            this.i = i;
            this.j = j;
        }
    }
}