[문제 풀이] 백준 14502번 연구소 JAVA

문제

  문제접근 방법   

해당 문제는 N x M 크기의 연구소가 존재할 때 연구소의 각 칸은 0은 빈칸, 1은 벽, 2는 바이러스를 의미한다. 

아무런 벽을 세우지 않는다면, 바이러스는 모든 빈칸으로 퍼져나갈 수 있다고 하는데 벽을 3개 세워 바이러스를 막는다. 

이때 더 이상 바이러스가 퍼질 수 없는 곳을 안전영역이라고 할때 안전영역의 크기가 최댓값인 경우를 구하는 프로그램을 작성하는 문제이다. 

처음 보자마자 dfs를 활용하여 탐색을 해야겠다고 생각했지만 한 번으로는 탐색이 어렵겠다고 생각을 해 방법을 고민했다. 

고민한 결과 dfs 안에서 dfs를 한번도 호출하는 방식으로 문제를 해결하기로 결정하였다. 코드는 다음과 같다.

 

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static int map[][];
    public static int safe=0;
    public static int safe2=0;
    public static int zero=0;
    public static List<int[]> list=new LinkedList<>();
    public static List<Integer> list2=new LinkedList<>();
    public static boolean visited[][];
    public static boolean visited2[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        map=new int[n][m];
        visited=new boolean[n][m];
        for(int i=0;i<3;i++){
            list.add(new int[2]);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                map[i][j]=s.nextInt();
                if(map[i][j]==0)zero++;
 
            }
        }
        
        

       dfs(0,0,0);

        System.out.println(safe);
    }
    
    public static void dfs(int x,int y,int depth){
        if(depth==3){
            visited2=new boolean[map.length][map[0].length];
            
            for(int i=0;i<3;i++){
                int xx=list.get(i)[0];
                int yy=list.get(i)[1];
                visited2[xx][yy]=true;
                map[xx][yy]=1;
            }
            int sum = 0;
            int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    if (map[i][j] == 2) {
                        for (int d = 0; d < 4; d++) {
                            int nx = i + dx[d], ny = j + dy[d];
                            if (0 <= nx && 0 <= ny && nx < map.length && ny < map[0].length) {
                                if (!visited2[nx][ny] && map[nx][ny] == 0) {
                                    visited2[nx][ny] = true;
                                    sum += len(nx, ny);
                                }
                            }
                        }
                    }
                }
            }

            for(int i=0;i<3;i++){
                int xx=list.get(i)[0];
                int yy=list.get(i)[1];
                map[xx][yy]=0;
            }
            
            safe=Math.max(safe,zero-3-sum);
            return;
        }
        
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                if(!visited[i][j]&&map[i][j]==0){
                    visited[i][j]=true;
                    list.get(depth)[0]=i;
                    list.get(depth)[1]=j;
                    dfs(i,j,depth+1);
                    visited[i][j]=false;
                }
            }
        }
    }
    
    public static int len(int x,int y){
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        visited2[x][y]=true;
        int cnt=1;
        if(map[x][y]==2){}
        for(int i=0;i<4;i++){
            int nx=dx[i]+x;
            int ny=dy[i]+y;
            if(nx>=0&&ny>=0&&nx<map.length&&ny<map[0].length){
                if(!visited2[nx][ny]&&map[nx][ny]==0){
                    cnt+=len(nx,ny);
                }
            }
        }
        
        return cnt;
        
    }
}

최종 코드의 전체적인 흐름을 설명하자면 

1. dfs를 통해 3개의 벽을 세운다 depth를 통해 3개를 선택한다.
2. 이후 3개를 벽으로 취급하고 바이러스를 찾는다.
3. 바이러스인 2를 찾으면 해당 좌표부터 퍼질 수 있는 크기를 구한다.
4. 이후 안전지역이 될 수 있는 zero의 수에서 벽의 크기 3과 바이러스가 퍼진 곳을 카운트한 값을 빼면 안전지역의 크기를 구할 수 있다.
5. 이를 반복하다보면 최종적으로 가장 큰 안전지대의 값이 safe에 저장되게 된다.

 

  마무리  

해당 문제는 알고리즘이나 문제의 방향성은 제시하기 쉽지만 구현이 어렵게 다가오는 문제였다. 여러 조건들과 조건 안에 조건들이 묶이면서 혼선이 왔던 것 같다. 또 처음에는 N x M크기에서 바이러스가 퍼진 곳만 제외하고 구하려는 실수를 범했는데

0인 곳만 안전지역 후보임을 염두하고 문제를 접근하는 것이 좋겠다.