[알고리즘][DFS][14502] 연구소

[알고리즘][DFS][14502] 연구소

문제

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

풀이

0은 공간, 1은 벽, 2는 바이러스입니다. n×m의 배열을 만들어 0,1,2로 입력받은 뒤 추가로 1인 벽을 3개 만들 수 있습니다. 추가적으로 세운 벽까지 포함하여 바이러스가 퍼지지 않는 안전영역의 최댓값을 구하면 됩니다. 

이 때, 어디에 벽을 세우느냐가 가장 큰 관건입니다. 벽 3개를 세우는 모든 경우를 돌면서 바이러스를 퍼뜨려보면 안전영역의 최댓값을 구할 수 있습니다. 쉽지 않았던 문제여서 다음에 다시 한 번 더 풀어봐야겠습니다ㅠㅠ

코드

package algorithm_DFS;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/* 삼성 SW 역량 테스트 기출 */
public class q_14502 {
    static int n;
    static int m;
    static int ans;
    static int[][] arr;
    static int[][] map = new int[9][9];
    static int dx[] = {1, -1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    
    public static class wall_n{
        int x, y;
        public wall_n(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }    
    
    public static void make_map() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                map[i][j] = arr[i][j];
            }
        }
    }
    public static void make_wall(int cnt) {
        //벽을 3개 세웠다면 바이러스를 퍼뜨려 count한다.
        if(cnt==3) {
            virus();
            return;
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(map[i][j]==1||map[i][j]==2) continue;
                map[i][j]=1;
                make_wall(cnt+1);
                map[i][j]=0; //backtracking
            }
        }
    }
    //바이러스 퍼뜨리기
    public static void virus() {
        int[][] temp = new int[n][m]; // 임시 배열을 만들어 바이러스를 퍼뜨려본다.
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                temp[i][j] = map[i][j];
            }
        }
        Queue<wall_n> q = new LinkedList<>();
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(temp[i][j]==2) {
                    q.add(new wall_n(i,j));
                }
            }
        }
        
        while(!q.isEmpty()) {
            wall_n now = q.remove();
            int x = now.x;
            int y = now.y;
            for(int i=0;i<4;i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
                if(temp[nx][ny]==2 || temp[nx][ny]==1) continue;
                temp[nx][ny]=2;
                q.add(new wall_n(nx, ny));
            }
        }
        
        //감염안된 지역 counting
        int cnt = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(temp[i][j]==0) ++cnt;
            }
        }
        ans = Math.max(ans, cnt);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        /*
         * 1. 연구소의 크기를 받는다. (n,m)
         * 2. nxm의 행렬을 입력받는다.
         * 3. 가능한 위쳉 벽 3개를 배치(dfs, backtracking)
         * 4. 바이러스를 퍼뜨린다.(dfs)
         * 5. 행렬의 0의 갯수를 counting 한다.
         */
        n = scan.nextInt();
        m = scan.nextInt();
        scan.nextLine();
        
        arr = new int[n][m];
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(arr[i][j]==2 || arr[i][j]==1) continue;
                make_map(); //벽이나 바이러스가 아닐경우 
                map[i][j]=1;
                make_wall(1);
                map[i][j]=0;
            }
        }
        System.out.println(ans);
    }
 
 
}