[BOJ - JAVA] 17142 - 연구소 3 (BFS, 백트래킹)

# 주소

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

17142번: 연구소 3

# 문제 

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;

public class Main {
    static int n, m, t;
    static int[][] arr;
    static int[][] ans;
    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, 1, -1, 0};
    static boolean[] visit;
    static int time = 0;
    static int result = Integer.MAX_VALUE;
    static int Tzero = 0;
    static boolean[] v;
    static Queue<Virus> queue = new LinkedList<>();
    static ArrayList<Virus> virus = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][n];
        visit = new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scan.nextInt();
                if(arr[i][j] == 2)
                    virus.add(new Virus(i,j));
                if(arr[i][j] == 0)
                    Tzero++;
            }
        }
        visit = new boolean[virus.size()];
        combination(0,0);
        System.out.println(result == Integer.MAX_VALUE ? -1 : result);
    }
    public static void combination(int start, int cnt){
        if(cnt == m){
            result = Math.min(result,bfs());
        }
        for(int i = start; i < virus.size(); i++){
            if (!visit[i]) {
                visit[i] =  true;
                combination(i + 1, cnt + 1);
                visit[i] = false;
            }
        }
    }
    public static int bfs(){
        queue = new LinkedList<>();
        boolean[][] v = new boolean[n][n];
        for(int i = 0; i < virus.size(); i++){
            if (visit[i]) {
                queue.add(new Virus(virus.get(i).x, virus.get(i).y, 0));
            }
        }
        int time = 0;
        int zero = 0;
        while (!queue.isEmpty()) {
            Virus now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n){
                    continue;
                }
                if(arr[nx][ny] == 1 || v[nx][ny])
                    continue;
                if (arr[nx][ny] != 1 && !v[nx][ny]) {
                    if (arr[nx][ny] == 0) {
                        zero++;
                        time = now.time + 1;
                    }
                    v[nx][ny] = true;
                    queue.offer(new Virus(nx,ny,now.time+1));
                }
            }
        }
        if(zero == Tzero)
            return time;
        return Integer.MAX_VALUE;
    }
}
class Virus{
    int x;
    int y;
    int time;
    Virus(int x, int y){
        this.x = x;
        this.y = y;
    }
    Virus(int x, int y, int time){
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

백트래킹과 bfs를 같이 써서 풀어야 합니다.

이 bfs문은 쉬웠는데 백트래킹 부분이 어려웠어요.

bfs와 dfs는 정말.. 어려운건 풀어도 풀어도 헷갈리네요.. ㅠㅠ

차근차근 보겠습니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
arr = new int[n][n];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        arr[i][j] = scan.nextInt();
        if(arr[i][j] == 2)
            virus.add(new Virus(i,j));
        if(arr[i][j] == 0)
            Tzero++;
    }
}

일단 제일 먼저 n과 m을 입력받습니다.

arr의 크기는 n x n의 배열이고 visit은 n크기의 boolean타입을 배열받습니다.

visit은 바이러스를 선택하는 수학에서 사용하는 조합의 중복을 배제하기 위해 선언합니다. 

그리고 arr를 이중for문으로 입력받는데, 만약 이 arr가 2이면 해당 인덱스를 Virus라는 ArrayList에 삽입합니다.

그리고 arr가 0일 때는 Tzero를 증가시키는데, 이 Tzero는 0이 나오는 횟수로서 마지막에 최종적으로 쓰입니다. 나중에 봅시다.

visit = new boolean[virus.size()];
    combination(0,0);
    System.out.println(result == Integer.MAX_VALUE ? -1 : result);
}

우리는 combination함수를 만들어서 사용할 것입니다.

이 combination함수는 바이러스들을 선택할 수 있는 모든 경우의 수로 선택하여 가능한 조합을 모두 만듭니다.

자 그럼 combination의 구조를 살펴봅시다.

public static void combination(int start, int cnt){
    if(cnt == m){
        result = Math.min(result,bfs());
    }
    for(int i = start; i < virus.size(); i++){
        if (!visit[i]) {
            visit[i] =  true;
            combination(i + 1, cnt + 1);
            visit[i] = false;
        }
    }
}

백트래킹중에서도 정말 간단한 백트래킹 구조입니다.

백트래킹이란, 이전 포스팅에 정말 많이 올렸었다가 요즘엔 잘 안나와서 뜸했는데 모든 경우의 수를 탐색할 때 사용하는 기법입니다.

이 visit이라는 boolean타입의 배열을 사용할 경우 중복되지 않는 경우의 수로 탐색할 수 있다는 특징을 가집니다.

따라서 구조를 살펴보면 cnt가 m이 됐을 때 이 result에 bfs의 값을 담을 것인데, 그 전에 cnt가 m이 되기 전이라면

for문을 이용하여 모든 경우를 탐색할 수 있습니다.

특히, combination(i + 1, cnt + 1)을 재귀함수로 실행하여 visit의 true, false를 바꾸어서 start지점을 계속 증가시킵니다.

그러다가 이 cnt도 1씩 증가시켰을 때 마침내 m값에 도달하면 (예제에선 3) result에 result와 bfs중 작은 것을 resul에 담는 것입니다.

그럼 이 bfs를 실행하면 어떤 값이 나와야 할까요?

public static int bfs(){
    queue = new LinkedList<>();
    boolean[][] v = new boolean[n][n];
    for(int i = 0; i < virus.size(); i++){
        if (visit[i]) {
            queue.add(new Virus(virus.get(i).x, virus.get(i).y, 0));
        }
    }

bfs의 구조입니다.

여기선 연구소의 인덱스를 탐색해야 하기 때문에 2차원 배열의 boolean타입의 v를 생성하고 for문을 이용하여 만약 visit이 있는 인덱스라면 이 queue에 모두 해당 인덱스들을 담습니다.

무슨 말이냐면, 2인 모든 지점들을 우리는 visit을 이용하여 조합을 써서 나타내었습니다. (위의 백트래킹)

여기서 visit이 true인 지점(예제에선 3개) 3개를 모두 queue에 담고 계속해서 그 지점 인근에 있는 0인 공간들을 바이러스로 퍼트린 후 최종적으로 처음에 0이었던 공간과 값이 바뀌는 인덱스들이 같아졌을 때 시간을 return하는 것이 목표입니다.

따라서 예제에선 3개의 바이러스가 퍼진다고 했으므로 queue에는 제일 처음엔 3개의 각각의 x,y가 담기는 것입니다.

int time = 0;
int zero = 0;
while (!queue.isEmpty()) {
    Virus now = queue.poll();
    for(int i = 0; i < 4; i++){
        int nx = now.x + dx[i];
        int ny = now.y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= n){
            continue;
        }
        if(arr[nx][ny] == 1 || v[nx][ny])
            continue;

자 그리고 time을 걸린 시간, zero를 바이러스가 퍼진 공간이라고 합시다.

while문 안으로 진입한 후 now를 queue에서 꺼내옵니다.

그리고 for문을 통해 총 4가지 방향의 인덱스를 모두 표현할 것인데, nx는 now.x + dx, ny = now.y + dy라고 합시다.

그랬을 때 새로 이동한 nx와 ny는 모두 0보다 작거나 n보다 크거나 같으면 continue시킵니다. (인덱스 밖)

그리고 arr가 1이거나 (벽에 부딪힘) 방문한 지역도 마찬가지로 continue 시킵니다.

if (arr[nx][ny] != 1 && !v[nx][ny]) {
        if (arr[nx][ny] == 0) {
            zero++;
            time = now.time + 1;
        }
        v[nx][ny] = true;
        queue.offer(new Virus(nx,ny,now.time+1));
    }
}

이후 모든 검열 과정이 끝났으면 arr가 1이 아닌 지점(0인 지점이겠죠?)과 v가 false일 때 zero값을 각각 늘립니다.

그리고 time을 now.time + 1하면 해당 인덱스일 때의 시간이 1씩 증가합니다! (그래서 queue를 쓰는 겁니다)

다 끝난 뒤 v값은 true로 바꾸어 주고 queue에는 새로운 nx,ny인덱스와 걸린 시간에 +1해줍니다.

여기서 헷갈릴 수 있는데, time의 값에 +1해준건 우린 정답을 출력할 때 쓸 코드입니다.

그리고 queue에 삽입할 now.time + 1은 queue에 담을 time입니다.

정확하게 시간을 나타내는 값이지만, time에 +1해주었다고 해서 now.time에 +1되는 것은 아닙니다.

왜냐하면 time은 실제 일반 변수의 값을 +1해준 것이고 now.time은 now라는 것의 안에 있는 time을 +1해준 것이기 때문입니다.

만약 여기서 time = now.time + 1에서 time++로 답을 작성해버리면, time의 값은 바이러스가 한 번 상하좌우로 퍼질  때 총 4만큼 증가하기 때문에 정답과 멀어집니다.

반드시 now.time에 +1해주는 습관을 길러서, 모든 작업이 끝나면 time에 1을 증가시키고 그것을 now로 연결시킨 뒤 queue에 담아주어야겠습니다. 

따라서 계속해서 queue에 담으면서 zero와 time을 증가시키다 보면 마침내 모든 인덱스의 값을 탐색할 수 있습니다

이 때 만약 zero == Tzero라면 (원래 0이었던 인덱스 개수와 바뀐 값의 개수가 같으면) time을 그대로 return합니다.

그런데 다르다면 그냥 Max_value를 리턴합니다.

그리고 갖고온 이 result를

if(cnt == m){
    result = Math.min(result,bfs());
}

원래의 result와 비교하면서 가장 작은 값을 result에 담게 됩니다.

그리고 갖고온 reuslt를

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

해당 구문을 입력하여 result를 출력합니다.

class Virus{
    int x;
    int y;
    int time;
    Virus(int x, int y){
        this.x = x;
        this.y = y;
    }
    Virus(int x, int y, int time){
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

저는 Virus 클래스를 오버로딩을 통해 구현했습니다.

ArrayList를 위해 사용할 class는 변수를 2가지로 뒀고 Queue를 사용하기 위해서는 변수를 3가지를 가져야 했습니다.

감사합니다.