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

---

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

---

🔍 문제 풀이

알고리즘 선택

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

순열 vs 조합 실행 시간 비교

실행 시간이 어마어마하게 차이가 나는 것을 볼수 있다.

[중복 순열 - 기존 방식]

기존 방식은 중복 순열이라 같은 3칸 조합도 순서만 바꿔 여러 번 탐색해 불필요한 연산이 많았다.

• buildWall에서 단순히 map[i][j] == 0이면 전부 돌면서 벽을 세움.
• 모든 좌표(i, j)에 대해 재귀 호출했기 때문에, 같은 3칸을 고르는 경우에도 순서만 다른 중복 경로를 전부 탐색
• 즉, 같은 3칸 조합을 3! 번씩 중복해서 탐색

[조합 - 개선된 방식]

• 2차원 배열에서 빈칸과 바이러스 좌표를 리스트로 저장한 뒤, 빈칸 좌표 리스트에서 3개를 조합으로 선택해 벽을 세우고 안전영역을 계산하는 방식이다.
• start를 이용해 같은 벽 조합을 한 번만 탐색 (조합 중복 제거)
• 또한 맵 복사 대신 방문 배열과 safe--를 사용해 실행 시간을 크게 줄였다

즉, 2차원 배열을 그대로 중첩 for문으로 돌면 순열처럼 중복이 생기고,
좌표를 인덱스로 변환해 조합을 만들면 중복 없이 한 번만 탐색 하게 된다!

문제 도식화

중복 순열

조합

💻 전체 코드

[방법 1] 중복 순열 (비효율)

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

public class Main {
    static int n, m;

    static int[][] map;
    static int[][] virusMap;
    static int maxSafeZone = Integer.MIN_VALUE;

    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];

        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);

    }

    // 벽 세우기
    static void buildWall(int depth) {
        if(depth == 3){
            spreadVirus();
            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(){
        // 1. 초기화
        Deque<int[]> dq = new ArrayDeque<>();
        virusMap = new int[n][m];

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

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

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

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

        safeZone(virusMap);

    }

    // 안전영역 계산 (모든 0인칸 개수 세기)
    static void safeZone(int[][] virusMap){
        int safeZone = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (virusMap[i][j] == 0) safeZone++;
            }
        }
        maxSafeZone = Math.max(maxSafeZone, safeZone);
    }
}

[방법 2] 조합 📌

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

public class Main {
    static int n, m;

    static int[][] map;
    static int[][] virusV;
    static int maxSafeZone = Integer.MIN_VALUE;

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

    static List<Pos> empties = new ArrayList<>();
    static List<Pos> viruses = new ArrayList<>();

    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());
                if (map[i][j] == 0) empties.add(new Pos(i, j));
                else if (map[i][j] == 2) viruses.add(new Pos(i, j));
            }
        }

        buildWall(0, 0); // 조합
        System.out.println(maxSafeZone);

    }

    // 벽 세우기 (DFS)
    static void buildWall(int depth, int start) {
        if(depth == 3){
            spreadViruses();
            return;
        }

        for(int i=start; i<empties.size(); i++){
            Pos p = empties.get(i);

            if(map[p.x][p.y] == 0){
                map[p.x][p.y] = 1;
                buildWall(depth + 1, i + 1);
                map[p.x][p.y] = 0;
            }
        }
    }

    // 바이러스 퍼트리기 (BFS)
    static void spreadViruses() {
        // 1. 초기화
        Deque<Pos> dq = new ArrayDeque<>();
        virusV = new int[n][m];

        // 2. 초기값
        int safe = empties.size() - 3; // 안전영역 초기값 = 전체 빈칸 - 벽 3개

        for (Pos v : viruses) {
            dq.offer(v);
            virusV[v.x][v.y] = 1;
        }

        // 3. 탐색
        while (!dq.isEmpty()) {
            Pos cur = dq.poll();

            // 3-1. 4방향, 범위
            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

                // 3-2. 미방문, 현재칸 0
                if (virusV[nx][ny] == 0 && map[nx][ny] == 0) {
                    virusV[nx][ny] = 1; // 감염됨
                    safe--; // 안잔영역 감소
                    dq.offer(new Pos(nx, ny));
                }
            }
        }

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

    static class Pos{
        int x;
        int y;

        Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}