[백준 / Java] 14502번 연구소

사용한 알고리즘 (DFS, BFS)

DFS

https://cobi-98.tistory.com/30

[필수 알고리즘] DFS 깊이 우선 탐색 (Stack 구조) 이해

 

BFS

https://cobi-98.tistory.com/36

[필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해

 

🔒 14502번 연구소

✔ 문제 설명

🚩 요구사항 분석

• 바이러스의 위치를 표현할 virus 생성자 생성 (VO)
• 상하좌우를 체크하기 위한 int 배열
• 벽을 세개 세우는 모든 경우의 수.(DFS)
• 최댓값을 찾기 위해 벽이 세워졌을 때, 복사본 배열을 하나 생성하여 그 배열에서 BFS를 진행하여 바이러스 전파
• 바이러스가 퍼준 뒤 안전 영역 크기 확인 
• 모든 경우의 수를 확인하면서 최댓값 출력

 

🔑 문제풀이

해당문제는 모든 경우의 수를 확인해 나가기 위한 dfs 깊이 우선 알고리즘과

벽을 세운뒤 상하좌우로 바이러스의 전파를 시키는 bfs 알고리즘을 사용했다.

 

bfs를 통해 바이러스를 전파시키고 안전영역 크기의 최댓값을 구해야 하기 때문에

map이라는 원본 연구소를 두고 copyMap 복사본 연구소를 추가함으로써 

벽을 3개 세우는 모든 경우의 수에 영향이 가지 않도록 하였다.

 

벽을 세 개 세웠다면, map이라는 int 배열을 copyMap 배열에 복사한다. 

 

배열을 복사하는 방법으로는 배열의 clone() 깊은 복사를 이용하였다.

ex) 깊은 복사 / 얕은 복사
1. 얕은 복사 : 복사한 배열이 원래 배열의 '주솟값'을 가져옴
2. 깊은 복사 : 복사한 배열이 원래 배열을 '그대로' 가져옴

 

복사된 배열에서 바이러스가 있는 위치를 꺼내 상하좌우를 확인하며 바이러스를 퍼트리고 안전영역을 확인한다.

 

모든 경우의 수를 탐색해 나가면서 안전 영역의 크기가 최댓값을 구하는 프로그램으로 진행되었다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int M;
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};
    public static int[][] map;
    public static int[][] copyMap;

    public static Queue<virus> queue = new LinkedList<virus>();
    public static int maxSafetyRoom = Integer.MIN_VALUE;

    static class virus{
        int x;
        int y;
        public virus(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    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(maxSafetyRoom);
    }


    public  static void dfs(int wallCnt) {
        if(wallCnt == 3) {
            bfs();
            return;
        }

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

    public static void bfs(){


        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(map[i][j] == 2) {
                    queue.offer(new virus(i,j));
                }
            }
        }

        copyMap = new int[N][M];

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

        while (!queue.isEmpty()){
            virus v = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = v.x + dx[i];
                int ny = v.y + dy[i];

                if(0 <= nx && nx <N && 0<= ny && ny <M) {
                    if(copyMap[nx][ny] == 0) {
                        copyMap[nx][ny] = 2;
                        queue.add(new virus(nx, ny));
                    }
                }
            }

        }

        funcSafeZone(copyMap);
    }

    private static void funcSafeZone(int[][] copyMap) {
        int safeZone =0;
        for(int i=0; i<N ; i++) {
            for(int j=0; j<M; j++) {
                if(copyMap[i][j] == 0) {
                    safeZone++;
                }
            }
        }

        maxSafetyRoom = Math.max(safeZone, maxSafetyRoom);

    }
}