JAVA [Algorithm] - 백준 14502 연구소

 

📝문제 설명

 

- 0은 빈칸, 1은 벽, 2는 바이러스

- 바이러스는 상하좌우로 움직이며 벽으로 가로막혀 있으면 퍼질 수 없다.

- 벽을 3개를 모두 세운 뒤 바이러스를 퍼트린 후, 0 빈칸의 개수가 최대인 값을 구하면 된다.

---

📢입출력 예시

 

---

✏️문제 풀이

package Baekjoon.Graph;

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 Baek14502 {

    static int[][] map;
    static int[][] copymap;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int countMax = Integer.MIN_VALUE;
    static int N, M, count;

    public static void main(String[] arg) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.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(bf.readLine());
            for(int j=0; j<M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());

            }
        }

        DFS(0);
        System.out.println(countMax);
    }

    private static void DFS(int depth){
        if(depth == 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(depth+1);
                    map[i][j] = 0;
                }
            }
        }
    }

    private static void BFS(){
        Queue<Virus> queue = new LinkedList<>();
        copymap = new int[N][M];

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

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

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

            int currentX = virus.x;
            int currentY = virus.y;

            for(int i=0; i<4; i++){
                int newX = currentX + dx[i];
                int newY = currentY + dy[i];

                if(newX >= 0 && newY >= 0 && newX < N && newY < M){
                    if(copymap[newX][newY] == 0){
                        copymap[newX][newY] = 2;
                        queue.offer(new Virus(newX, newY));
                    }
                }
            }
        }

        countSafeZone(copymap);
    }

    private static void countSafeZone(int[][] copy){
        count = 0;

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(copy[i][j] == 0){
                    count++;
                }
            }
        }
        countMax = Math.max(countMax, count);
    }
    
    private static class Virus{
        int x;
        int y;
        Virus(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

 

- 이 문제는 DFS, BFS 두개의 알고리즘을 제대로 알고있는지 묻는 문제라고 생각한다.

- DFS를 사용하여 기둥을 세울 수 있는 모든 조건들을 파악하고, 3개가 세워진다면 BFS로 진입한다.

- BFS에서 바이러스를 퍼트린 후, 안전지대를 개수를 파악한다.

- BFS가 끝나면 DFS로 돌아와 MAP을 원상복구한다.

- BFS를 수행할 때 map을 copymap으로 복제를 하는데 그 이유는 map을 그대로 유지하면 기존 맵의 정보가 달라지기 때문이다.

---

💡새로 알게된 점

- DFS와 BFS 알고리즘을 언제 적절히 사용해야 되는지 깨달아버렸다

 

---