[BOJ] 14502 연구소 - Java

✨ BFS + DFS + 완전탐색

https://www.acmicpc.net/problem/14502

14502번: 연구소

---

📍고려해야할 점

• 벽을 3개 세운다. ➔ 일일이 3개의 벽을 세워본 후 바이러스를 퍼뜨려 안전영역이 최대인 경우를 구한다. (백트래킹 + 완전탐색)
• 벽을 3개 세운 후 바이러스가 퍼지는 경우는 다양하므로 복사본을 만들어서 구한다. 

 

🕹️ 풀이과정

1️⃣ 바이러스와 벽이 있는 곳의 정보를 2차원 배열에 저장한다. 

2️⃣ 벽을 세운다. ➔ 3개의 벽을 세워야 하므로 조합을 생각하면 된다. DFS와 백트래킹을 이용해 벽을 세우면 된다. 

3️⃣ 3개의 벽이 세워지면 바이러스를 퍼뜨린다. 바이러스가 있는 곳부터 시작해 퍼지므로 바이러스가 있는 곳의 정보를 따로 저장해야 한다. 

4️⃣ 3개의 벽이 세워지는 경우는 매번 달라지므로 2차원 배열을 복사해서 사용한다. 

5️⃣ 바이러스가 다 퍼졌으면 안전영역을 구한다. 

 

 

 

👩‍💻 전체 코드 

public class BOJ_14502_연구소 {

    static int N, M;
    static int max = Integer.MIN_VALUE;
    static int[][] lab;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    static class Info{
        int x, y;

        public Info(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    //DFS
    static void makeWall(int depth){

        if (depth == 3) {
            spreadVirus();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (lab[i][j] ==0) {
                    lab[i][j]=1;
                    makeWall(depth + 1);
                    lab[i][j]=0;
                }
            }
        }
    }

    // BFS
    static void spreadVirus(){

        Queue<Info> queue = new LinkedList<>();
        int[][] virusMap = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                virusMap[i][j] = lab[i][j];
                if (virusMap[i][j] == 2) {
                    queue.add(new Info(i, j));
                }
            }
        }

        while (!queue.isEmpty()) {
            Info now = queue.poll();

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

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

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

        max = Math.max(cnt, max);

    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        lab = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                lab[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        makeWall(0);
        bw.write(max + " ");
        bw.flush();
        bw.close();
    }
}