백준-14502번/연구소(java)

 

 

문제 이해

 

N X M 크기의 이차원 배열의 구성 요소

0 ==> 빈공간

1 ==> 벽

2 ==> 바이러스( 상하좌우로 이동 가능)

 

조건

1) 바이러스는 상하좌우로만 이동 가능

2) 벽은 무조건 3개만 세울 수 있다.

 

문제를 풀기 위해서는 임의의 빈 공간에 벽을 3개 세운 다음 바이러스를 퍼뜨리고 연구소에서 바이러스가 없는 빈 공간의 갯수를 세면 된다.

 

구현 로직

 

벽 세우기 ==> 임의의 빈 공간에 벽을 3개 세울 수 있는 모든 경우를 고려 해야 하므로 DFS로 구현

바이러스 퍼뜨리기 ==> 상하좌우로 이동하는 것을 구현하기 위해 BFS로 구현

 

 

문제 해결

 

 

DFS ==> 3개의 벽을 세울수 있는 경우를 모두 구하기

public static void dfs(int wall){ //벽 세우기
    if(wall==3){
        bfs();
        return;
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(arr[i][j]==0){
                arr[i][j]=1;
                dfs(wall+1);
                arr[i][j]=0;
            }
        }
    }
}

벽을 3개 모두 세웠을 경우 bfs를 수행

 

BFS ==> 바이러스를 퍼뜨리고 안전한 곳의 갯수 구하기

public static void bfs(){  //바이러스 퍼뜨리기
    Queue<int[]> queue = new LinkedList<>();
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(arr[i][j]==2){
                queue.add(new int[]{i,j});
            }
        }
    }

    int[][] copyArr = new int[N][M];

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            copyArr[i][j]=arr[i][j];
        }
    }

    while(!queue.isEmpty()){
        int[] point=queue.poll();
        int pointX=point[0];
        int pointY=point[1];

        for(int i=0; i<4; i++){
            int nextX=pointX+dx[i];
            int nextY=pointY+dy[i];
            if(nextX>=0 && nextY>=0 && nextX<N && nextY<M){
                if(copyArr[nextX][nextY]==0) {
                    queue.add(new int[]{nextX,nextY});
                    copyArr[nextX][nextY] = 2;
                }
            }

        }
    }

    int count = 0;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(copyArr[i][j]==0){
                count++;
            }
        }
    }

    if(count>Max){
        Max=count;
    }

}

주의할 점 : 바이러스를 퍼뜨리면 기존의 입력받은 배열을 수정해야 하므로 카피된 배열을 이용해서 거기서 바이러스를 퍼뜨리고 안전한 곳을 찾아야 한다.

 

 

<전체 코드>

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Problem14502 {
    static int N,M;
    static int arr[][];
    static int[] dx={-1,1,0,0};
    static int[] dy={0,0,-1,1};
    static int Max =Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        N=scanner.nextInt();
        M=scanner.nextInt();
        arr=new int[N][M];

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                arr[i][j]=scanner.nextInt();
            }
        }

        dfs(0);
        System.out.println(Max);
    }

    public static void dfs(int wall){ //벽 세우기
        if(wall==3){
            bfs();
            return;
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(arr[i][j]==0){
                    arr[i][j]=1;
                    dfs(wall+1);
                    arr[i][j]=0;
                }
            }
        }
    }

    public static void bfs(){  //바이러스 퍼뜨리기
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(arr[i][j]==2){
                    queue.add(new int[]{i,j});
                }
            }
        }

        int[][] copyArr = new int[N][M];

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                copyArr[i][j]=arr[i][j];
            }
        }

        while(!queue.isEmpty()){
            int[] point=queue.poll();
            int pointX=point[0];
            int pointY=point[1];

            for(int i=0; i<4; i++){
                int nextX=pointX+dx[i];
                int nextY=pointY+dy[i];
                if(nextX>=0 && nextY>=0 && nextX<N && nextY<M){
                    if(copyArr[nextX][nextY]==0) {
                        queue.add(new int[]{nextX,nextY});
                        copyArr[nextX][nextY] = 2;
                    }
                }

            }
        }

        int count = 0;

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(copyArr[i][j]==0){
                    count++;
                }
            }
        }

        if(count>Max){
            Max=count;
        }

    }
}