백준 14502 연구소 Java

완전 탐색 문제인 연구소이다.

1번은 벽이고 2번은 바이러스이고 0번은 아무것도 아니다.

2번 바이러스는 상하좌우가 0번인 경우에만 계속해서 옮겨간다.

 

1번인 벽을 3개 더 삽입해서 얻을 수 있는 안전 영역(0의 개수)을 출력하면 되는 문제이다.

 

1을 3개 삽입하는 것은 백트래킹으로 모든 경우를 해보면 되고

바이러스가 퍼지는 것은 BFS로 구현한다. 바이러스가 다 퍼졌다면 

0의 개수를 세서 가장 0의 개수가 많이 나올 때를 출력하면 된다.

 

정리하자면

1. 1이 들어갈 수 있는 모든 경우를 백트래킹으로 해본다.

2. 1이 3번 삽입 됐을 때 바이러스를 BFS로 퍼트려본다.

3. 0의 개수를 세서 최대값을 출력한다.

 

주의할 점은 바이러스를 퍼트릴 때 입력받은 a배열에 퍼트릴 경우

다음에 오는 경우들을 체크할 수 없다는 점이다.

그래서 a배열을 b배열에 복사한 후 b배열에 바이러스를 퍼트린다.

 

0의 개수의 최댓값은 전역변수를 통해 구했다.

 

처음엔 백트래킹을 i번째 인덱스를 사용하는 경우와 사용하지 않는 경우를

나눠서 탐색했는데 다른 분들보다 너무 오래 걸리는 것 같아서

다른 분이 한 탐색방법도 같이 공부했다.

i번부터 최대값까지 for문으로 재귀 호출을 하며 계속해서 끝까지 사용하는 경우를

탐색하는 것이였다.

 

1. 수를 사용하는 경우와 사용하지 않는 경우를 나누어서 재귀 호출로 탐색

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Q14502_ver2 {
 
    static int [] dx = {1, -1, 0, 0};
    static int [] dy = {0, 0, 1, -1};
    static int max = 0;
    
    public static int area(int[][]a) {
        Queue<Pos4> q = new LinkedList<>();
        int [][] clone = new int[a.length][a[0].length];
        for(int i=0; i<a.length; i++) {
            for(int j=0; j<a[0].length; j++) {
                clone[i][j] = a[i][j];
                if(a[i][j] == 2) {
                    q.add(new Pos4(i, j));
                }
            }
        }
        
        while(!q.isEmpty()) {
            Pos4 p  = q.poll();
            int x = p.x;
            int y = p.y;
            
            for(int k=0; k<4; k++) {
                if(x+dx[k]>=0 && x+dx[k]<a.length) {
                    if(y+dy[k]>=0 && y+dy[k]<a[0].length) {
                        if(clone[x+dx[k]][y+dy[k]] == 0) {
                            clone[x+dx[k]][y+dy[k]] = 2;
                            q.add(new Pos4(x+dx[k], y+dy[k]));
                        }
                    }
                }
            }
        }
            
        int cnt = 0;
        for(int i=0; i<a.length; i++) {
            for(int j=0; j<a[0].length; j++) {
                if(clone[i][j] == 0) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    public static void backtrack(int [][] a, int index, int cnt) {
        if(cnt == 3) {
            max = Math.max(max, area(a));
            return;
        }
        if(index == a.length * a[0].length) return;
        
        int x = index / a[0].length;
        int y = index % a[0].length;
        
        if(a[x][y] == 0) {
            a[x][y] = 1;
            backtrack(a, index+1 , cnt+1); //사용하는 경우
            a[x][y] = 0; 
            backtrack(a, index+1 , cnt); //사용하지 않는 경우
        } else {
            backtrack(a, index+1 , cnt);
        }
            
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int [][] a = new int[n][m];
        boolean [][] b = new boolean[n][m];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                a[i][j] = scan.nextInt();
            }
        }
        backtrack(a, 0, 0);
        System.out.println(max);
        
    }
}
class Pos4 {
    int x;
    int y;
    
    public Pos4(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

2. i부터 범위 끝가지 사용하는 경우를 for문을 통한 재귀호출로 탐색

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
 
public class Q14502 {
    static int [] dx = {1, -1, 0, 0};
    static int [] dy = {0, 0, 1, -1};
    static int max = 0;
    
    public static int area(int[][]a) {
        Queue<Pos5> q = new LinkedList<>();
        int [][] clone = new int[a.length][a[0].length];
        for(int i=0; i<a.length; i++) {
            for(int j=0; j<a[0].length; j++) {
                clone[i][j] = a[i][j];
                if(a[i][j] == 2) {
                    q.add(new Pos5(i, j));
                }
            }
        }
        
        while(!q.isEmpty()) {
            Pos5 p  = q.poll();
            int x = p.x;
            int y = p.y;
            
            for(int k=0; k<4; k++) {
                if(x+dx[k]>=0 && x+dx[k]<a.length) {
                    if(y+dy[k]>=0 && y+dy[k]<a[0].length) {
                        if(clone[x+dx[k]][y+dy[k]] == 0) {
                            clone[x+dx[k]][y+dy[k]] = 2;
                            q.add(new Pos5(x+dx[k], y+dy[k]));
                        }
                    }
                }
            }
        }
            
        int cnt = 0;
        for(int i=0; i<a.length; i++) {
            for(int j=0; j<a[0].length; j++) {
                if(clone[i][j] == 0) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    public static void backtrack(int [][] a, int index, int cnt) {
        if(cnt == 3) {
            max = Math.max(max, area(a));
            return;
        }
        if(index == a.length * a[0].length) return;
        
        for(int i=index; i<a.length * a[0].length; i++ ) {
            int x = i / a[0].length;
            int y = i % a[0].length;
            if(a[x][y] == 0) {
                a[x][y] = 1;
                backtrack(a, i+1, cnt+1);
                a[x][y] = 0;
            }
        }
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int [][] a = new int[n][m];
        boolean [][] b = new boolean[n][m];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                a[i][j] = scan.nextInt();
            }
        }
        backtrack(a, 0, 0);
        System.out.println(max);
        
    }
}
class Pos5 {
    int x;
    int y;
    
    public Pos5(int x, int y) {
        this.x = x;
        this.y = y;
    }
}