[백준] 14502: 연구소 - JAVA [자바]

안녕하세요.

오늘은 14502번: 연구소 문제를 풀어보도록 하겠습니다.

요즘 목표 중 하나가 깃허브에 멋지게 플레티넘 티어를 달아두는 건데요. . .
그래서 다시 코드트리에서 백준으로 넘어와 문제를 풀고 있습니다.

 

특히 BFS 문제는 알고리즘에서 가장 빈번하게 출제되는 유형 중 하나라 꼭 잡고 가야 한다고 생각했습니다.
이번에 다룬 연구소(14502) 문제는 전형적인 완전탐색 + 시뮬레이션 + DFS 유형이라 복습하기에 적합했습니다.

 

 

📌 접근

저는 이 문제를 크게 3가지 단계로 나눴습니다.

 

1. 빈 칸 3곳을 선택해 벽 세우기 (buildWall)

2. 바이러스 퍼뜨리기 (spreadVirus)

3. 안전 영역 카운팅 (getSafeArea)

 

 

💻 풀이

// hyeblee
import java.util.*;
import java.io.*;

public class Hyeblee {

  public static class Node {

    int y, x;

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

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

  public static int n, m;
  public static int[][] grid;
  public static int[][] tmp;
  public static boolean[][] visited;
  public static List<Node> viruses = new ArrayList<>();
  public static int max = 0;

  // 0인 칸 3곳 선택하기
  public static void buildWall(int depth) {
    if (depth == 3) { // 벽 3곳 다 세우면
      // 바이러스 퍼뜨리기
      spreadVirus();
//      for(int i=0;i<n;i++) {
//        for(int j=0;j<m;j++) {
//          System.out.print(grid[i][j] + " ");
//        }
//        System.out.println();
//      }
//      System.out.println("==============\n\n");
      // 안전 영역 세기
      max = Math.max(getSafeArea(), max);
      return;
    }

    // 벽 세울 수 있는 곳 정해서 다음벽 세우기로 넘어가기
    for (int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        if (grid[i][j] == 0) {
          grid[i][j] = 1; // 벽세우기
//          System.out.print(i+", " + j + " -- ");
          buildWall(depth + 1);
          grid[i][j] = 0; // 원래대로 돌리기
        }
      }
    }
  }

  // 바이러스 퍼뜨리기
  public static void spreadVirus() {
    visited = new boolean[n][m];
    for(int i=0;i<n;i++) {
      for(int j=0;j<m;j++) {
        tmp[i][j] = grid[i][j];
      }
    }

    for(int i=0;i<viruses.size();i++) {
      int y = viruses.get(i).y;
      int x = viruses.get(i).x;
      if (!visited[y][x]) {
        dfs(y, x);
      }
    }
  }

  // 2인 영역 확장하기
  public static void dfs(int y, int x) {
    visited[y][x] = true;
    for (int i = 0; i < 4; i++) {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (!inRange(ny, nx)) {
        continue;
      }
      if (tmp[ny][nx] != 1 && !visited[ny][nx]) { // 벽이 아니면 탐색 진행 가능
        tmp[ny][nx] = 2;
        dfs(ny, nx);
      }
    }
  }

  public static boolean inRange(int y, int x) {
    return 0 <= y && y < n && 0 <= x && x < m;
  }

  // 안전 영역 세기
  public static int getSafeArea() {
    int safeArea = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (tmp[i][j] == 0) {
          safeArea++;
        }
      }
    }

    return safeArea;
  }


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

    grid = new int[n][m];
    tmp = new int[n][m];
    visited = new boolean[n][m];

    for(int i=0;i<n;i++) {
      st = new StringTokenizer(br.readLine());
      for(int j=0;j<m;j++) {
        grid[i][j] = Integer.parseInt(st.nextToken());
        if (grid[i][j] == 2) {
          viruses.add(new Node(i, j));
        }
      }
    }

    buildWall(0);

    System.out.println(max);
  }

}

 

위 풀이는 제가 처음 작성한 풀이입니다.

빠른 탐색을 위해 BFS가 아닌 DFS를 사용했습니다.

 

벽을 3개 고르는 연산의 시간 복잡도는,  O((N*M)^3)

바이러스를 퍼뜨리는 연산의 시간복잡도는 O(N*M)

전체적으로는 O((N*M)^3 * (N*M))의 시간복잡도를 갖습니다.

다행히 입력 크기가 N, M <= 10 정도일 때는 연산 횟수가 대략 천만 번 정도로, 충분히 2초 내에 처리할 수 있습니다.

(참고로 일반적으로 2초 정도면 약 1~2억 연산까지 처리할 수 있습니다.)

 

 

🤔 고민했던 점 & 어려웠던 부분

DFS는 재귀 호출 깊이가 증가하면 스택 오버플로우가 발생할 위험이 있고, 재귀 호출 순서 때문에 실제 grid 상태를 추적하기가 비직관적이라는 단점이 있습니다.

또한, 이전에는 grid 배열을 하나씩 복사하며 상태를 관리했는데, 이는 연산량이 많아 효율적이지 않았습니다.

 

그래서 BFS + System.arraycopy 를 적용하여 최적화했습니다.

BFS는 큐를 사용하여 바이러스 퍼짐을 단계별로 처리하기 때문에 grid 상태가 명확하고, 재귀 호출로 인한 스택 문제도 발생하지 않습니다.

또한 System.arraycopy를 사용하면 배열을 빠르게 복사할 수 있어, 매번 새 배열을 생성하는 것보다 훨씬 효율적입니다.

최적화를 적용한 코드는 다음과 같습니다.

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

public class Main {

    public static class Node {
        int y, x;

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

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

    public static int n, m;
    public static int[][] grid;
    public static int[][] tmp;
    public static List<Node> viruses = new ArrayList<>();
    public static int max = 0;

    public static void buildWall(int depth) {
        if (depth == 3) {
            spreadVirus();
            max = Math.max(getSafeArea(), max);
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    grid[i][j] = 1;
                    buildWall(depth + 1);
                    grid[i][j] = 0;
                }
            }
        }
    }

    // BFS를 이용한 바이러스 확산
    public static void spreadVirus() {
        tmp = new int[n][m];
        for (int i = 0; i < n; i++) {
            System.arraycopy(grid[i], 0, tmp[i], 0, m);
        }

        Queue<Node> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];

        for (Node virus : viruses) {
            queue.add(virus);
            visited[virus.y][virus.x] = true;
        }

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (int dir = 0; dir < 4; dir++) {
                int ny = cur.y + dy[dir];
                int nx = cur.x + dx[dir];

                if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if (tmp[ny][nx] == 0 && !visited[ny][nx]) {
                    tmp[ny][nx] = 2;
                    visited[ny][nx] = true;
                    queue.add(new Node(ny, nx));
                }
            }
        }
    }

    public static int getSafeArea() {
        int safeArea = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (tmp[i][j] == 0) safeArea++;
        return safeArea;
    }

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

        grid = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                if (grid[i][j] == 2) viruses.add(new Node(i, j));
            }
        }

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

 

만약 N, M >= 20이라면 완전 탐색으로는 풀기 어렵습니다.

왜냐면 (N*M)^3만 해도 이미 6천만번 이라서, 시간초과가 납니다.

이런 경우에는 다음과 같은 방법들을 사용하여 최적화할 수 있습니다.

 

1. 벽 후보(빈 칸) 좌표 미리 리스트화

• 0인 칸만 탐색 → 불필요한 반복 제거

List<Node> empty = new ArrayList<>();
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (grid[i][j] == 0) empty.add(new Node(i, j));
    }
}

 

 

 

2. 가지치기

• 이미 안전 영역이 이전 최대값보다 작으면 조기 종료
• 바이러스 확산 중 안전 영역이 0이 되면 더 이상 계산하지 않음
  (초기 안전 영역의 개수에서, 벽을 세울 때와 바이러스가 퍼질때 -1씩 감소)

if (currentSafeArea + remainingEmpty < maxSafeArea) return;

 

 

 

 

3. bitmask 활용

• 400칸 중 벽 3개 선택 → bitmask로 조합 계산

int emptyCount = emptyCells.size(); // 빈 칸 좌표 리스트

for (int mask = 0; mask < (1 << emptyCount); mask++) { 
    // 1 << emptyCount → 2^emptyCount, 모든 빈칸 조합을 비트마스크로 표현
    // mask는 각 조합을 0~2^emptyCount-1로 나타냄

    if (Integer.bitCount(mask) != 3) continue; 
    // mask에서 1의 개수가 3이 아니면 벽 3개가 선택되지 않은 조합 → 스킵

    // 선택된 빈 칸 확인
    List<Node> walls = new ArrayList<>();
    for (int i = 0; i < emptyCount; i++) {
        if ((mask & (1 << i)) != 0) { 
            // 1 << i → i번째 비트를 1로 만듦
            // mask & (1 << i) != 0 → i번째 빈 칸이 선택되었는지 확인
            walls.add(emptyCells.get(i)); // 선택된 빈 칸 좌표 추가
        }
    }

    // walls에 선택된 3개의 벽 좌표가 들어있음
    // grid에 벽 세우고 시뮬레이션 진행 가능
}