[Algorithm/Java] 백준 14502번 - 연구소

---

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

---

🔍 문제 풀이

문제 도식화

큰돌의 터전님 유튜브를 보고 문제 도식화를 해봤는데 쉽게 문제를 풀어나갈 수 있었다.

앞으로 문제를 풀기 전에 먼저 도식화/시각화 -> 로직 구조 설계 -> 구현 순으로 접근하자.
이전에 풀었던 문제도 다시 이 접근법으로 풀어봐야겠다.

알고리즘 선택

• 벽을 3개 세우는 건 조합을 모두 탐색해야 하기 때문에 DFS 기반의 백트래킹으로 구현했고,
• 벽이 세워진 뒤 바이러스 전파는 동시에 여러 방향으로 퍼지는 특성을 고려해 BFS로 처리했다.

놓친 점

원본 map을 복사해야한다.

• 벽 3개가 세워질 때마다 BFS가 실행됨
• 벽이 세워진 map을 복사해, 원본 map을 유지하고 copyMap에서만 BFS를 수행해야 함

for (int i = 0; i < n; i++) {
    copyMap[i] = map[i].clone();  // 배열 한 줄씩 복사 (깊은복사)
}

💻 전체 코드

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

public class Main {
    static int n, m;
    static int maxSafeZone = 0;

    static int[][] map;
    static int[][] copyMap;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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];
        copyMap = 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());
            }
        }

        buildWall(0);
        System.out.println(maxSafeZone);
    }

    // 벽 3개 세우기
    static void buildWall(int depth){
        if(depth == 3){
            spreadVirus(); // 벽 3개 세운 경우에만 시뮬레이션 실행
            return;
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] == 0){
                    map[i][j] = 1; // 벽 세우기
                    buildWall(depth + 1); // 다음 벽으로
                    map[i][j] = 0; // 백트래킹
                }
            }
        }
    }

    // 바이러스 퍼트리기
    static void spreadVirus() {
        // 복제(헷갈림)
        for (int i = 0; i < n; i++) {
            copyMap[i] = map[i].clone(); // 배열 한 줄씩 복사 (깊은복사)
        }

        Deque<int[]> dq = new ArrayDeque<>();

        // 바이러스 위치 큐에 추가
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyMap[i][j] == 2) {
                    dq.offer(new int[]{i, j});
                }
            }
        }

        while (!dq.isEmpty()) {
            int[] cur = dq.poll();
            int cx = cur[0];
            int cy = cur[1];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (copyMap[nx][ny] == 0) {
                    copyMap[nx][ny] = 2;
                    dq.offer(new int[]{nx, ny});
                }
            }
        }

        // 안전 영역 계산
        int safeZone = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyMap[i][j] == 0) safeZone++;
            }
        }

        maxSafeZone = Math.max(maxSafeZone, safeZone);
    }
}