백준 14502번 : 연구소 java

이 문제는 dfs와 bfs를 이용하여 푸는 브루트포스 문제입니다.

소스 코드를 보면서 설명하도록 하겠습니다.

---

import java.util.*;
import java.io.*;

public class Main{
    static int N, M;
    static int[][] map;
    static int max = Integer.MIN_VALUE;
    static int[] drow = {0, 0, 1, -1};
    static int[] dcol = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j<M; j++)
                map[i][j]= Integer.parseInt(st.nextToken());
        }

        dfs(0);

        System.out.println(max);
    }

    static void dfs(int count){
        if(count == 3){
            bfs();
            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;
                dfs(count+1);
                map[i][j] = 0;
            }
        }
    }

    static void bfs(){
        Queue<rowCol> ll = new LinkedList<>();

        for(int i = 0; i<N; i++)
            for(int j = 0; j<M; j++)
                if(map[i][j] == 2)
                    ll.offer(new rowCol(i, j));

        //원본 데이터를 훼손하지 않기 위해서 새로운 배열에 데이터 저장
        // sum = map을 하지 않는 이유는 shallow copy가 일어나기 때문에 clone()으로 deep copy
        int[][] sub = new int[N][M];

        for(int i = 0; i<N; i++)
            sub[i] = map[i].clone();

        while(!ll.isEmpty()){
            rowCol rc = ll.poll();

            for(int i = 0; i<4; i++){
                int dr = rc.row + drow[i];
                int dc = rc.col + dcol[i];

                if(dr<0||dc<0||dr>=N||dc>=M)
                    continue;

                if(sub[dr][dc] == 0){
                    ll.offer(new rowCol(dr, dc));
                    sub[dr][dc] = 2;
                }
            }
        }

        check(sub);
    }

    static void check(int[][] sub){
        int cnt = 0;

        for(int i = 0; i<N; i++)
            for(int j = 0; j<M; j++)
                if(sub[i][j] == 0)
                    cnt++;

        max = Math.max(max, cnt);
    }
}

//좌표를 저장하기 쉽게 하지 위해서 새로운 클래스 생성
class rowCol{
    int row, col;
    rowCol(int row, int col){
        this.row = row;
        this.col = col;
    }
}

우선 이 문제에서는 비어 있다는 의미인 0이 들어가 있는 칸에서는 아무 데나 벽을 칠 수 있습니다.

그럼 우리는 어디에 벽을 세워야 바이러스가 가장 적게 퍼져서 안전 구역이 많아지는지를 찾아야 합니다.

이 벽을 세울 위치를 찾기 위해서 저는 dfs를 사용하였습니다.

static void dfs(int count){
    if(count == 3){
        bfs();
        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;
            dfs(count+1);
            map[i][j] = 0;
        }
    }
}

이와 같이map[i][j]번에 0이 들어있으면 map[i][j] = 1을 이용하여 벽을 세워주었고 재귀를 활용하여 차례대로 벽이 세워지게 하였습니다.

그리고 count 즉 벽을 3개 세우면 bfs함수를 실행하여 바이러스가 바이러스 주변으로 퍼졌을 때 안전영역이 얼마나 남는지를 구하여 안전영역이 가장 많을 때를 구하였습니다.

위 문제의 예제 2번을 이용하여 문제가 해결되는 과정을 그림으로 보여드리겠습니다.

 

 

2번의 초기 상황은 왼쪽의 그림과 같습니다.

벽은 파란 블록으로 표시하였고
바이러스는 빨간 블럭으로 표시하였습니다.

 

 

왼쪽의 그림이 처음 dfs를 사용하였을 때입니다.

새로 만든 벽은 초록색으로 표시하였습니다.

count가 3이 되어 bfs로 처음 넘어갈 때의
그림입니다.

 

 

 

이 상황에서 bfs를 사용하면 다음과 같은 그림으로 변합니다.

이 상황에서는 안전영역이 없어 max가 0입니다.

 

 

 

다음 dfs에서 count가 3이 되었을 때의
상황입니다.

이때도 똑같이 bfs를 사용하면 안전영역은 없어 max가 0일 것입니다.

 

 

이제 dfs가 조금 더 많이 작동되었을 때를 예시로 가져오겠습니다.

 

 

새로 생성된 벽들이 이런 모양일 때 바이러스가 퍼지도록 bfs를 실행해보도록 하겠습니다.

 

 

 

바이러스가 퍼지면 다음과 같은 모양이
됩니다.

이 때 안전영역의 개수는 위에 6개 아래 3개로 총 9개가 됩니다.

 

 

이 문제는 이렇게 0이 있는 칸들에 dfs를 이용하여 벽이 생성되어 1이 들어갔을 때 bfs함수를 이용하여 바이러스가 얼마나 퍼지는지를 확인하여 안전영역인 0이 얼마나 많이 있는지를 찾는 문제입니다.