14502번: 연구소

문제

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있습니다. 연구소는 빈 칸(0), 벽(1), 바이러스(2)로 이루어져 있습니다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있습니다. 새로 세울 수 있는 벽의 개수는 무조건 3개이며, 꼭 3개를 세워야 합니다. 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 합니다. 안전 영역 크기의 최댓값을 구하는 문제입니다.

• 입력: 첫째 줄에 세로 크기 N과 가로 크기 M이 주어집니다. (3 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에 연구소의 지도가 주어집니다.
• 출력: 얻을 수 있는 안전 영역의 최대 크기를 출력합니다.

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

풀이: 조합 완전탐색과 BFS 시뮬레이션

지도 크기가 최대 8x8 = 64칸으로 매우 작습니다. 빈 칸 중에서 3개를 고르는 모든 경우의 수를 확인하고, 각각의 경우에 대해 바이러스를 퍼뜨려보는 브루트포스 시뮬레이션으로 해결할 수 있습니다.

1. 빈 칸 리스트 추출: 입력을 받을 때 지도의 값이 0(빈 칸)인 곳의 좌표를 List<Node> list에 모두 담아둡니다. 이를 통해 전체 맵을 돌며 빈 칸을 찾는 수고를 덜고, 리스트의 인덱스만으로 조합을 쉽게 구성할 수 있습니다.
2. 3개의 벽 세우기 (완전탐색 및 백트래킹): 3중 for문을 사용하여 빈 칸 리스트에서 중복 없이 3개의 좌표를 고릅니다. 고른 좌표를 일시적으로 벽(1)으로 바꾼 뒤(makeWall), 안전 영역을 구하고(getSafetyArea), 다음 경우의 수를 탐색하기 위해 다시 빈 칸(0)으로 되돌립니다(removeWall).
3. 바이러스 확산 시뮬레이션 (BFS): 바이러스(2)가 있는 모든 위치를 큐에 넣고 BFS를 실행합니다. 원본 지도를 보존해야 하므로 visited 배열을 사용하여 바이러스가 퍼진 경로를 마킹합니다. 상하좌우로 이동할 때, 맵을 벗어나지 않고 빈 칸(0)이면서 아직 방문하지 않은 곳으로만 퍼지게 합니다.
4. 안전 영역 계산: BFS 확산이 끝난 후 지도 전체를 순회하며 빈 칸(0)이면서 바이러스가 도달하지 못한(!visited) 곳의 개수를 세어 최댓값(ans)을 갱신합니다.

코드

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

public class Main {
    static int n, m;
    static int[][] a;
    static List<Node> list = new ArrayList<>();
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
       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());

       a = new int[n][m];
       for (int i = 0; i < n; i++) {
          st = new StringTokenizer(br.readLine());
          for (int j = 0; j < m; j++) {
             a[i][j] = Integer.parseInt(st.nextToken());
             // 빈 칸(0)의 좌표를 리스트에 미리 저장
             if (a[i][j] == 0) {
                list.add(new Node(i, j));
             }
          }
       }

       int ans = 0;
       // 빈 칸 중 3개를 고르는 조합 (완전탐색)
       for (int i = 0; i < list.size() - 2; i++) {
          for (int j = i + 1; j < list.size() - 1; j++) {
             for (int k = j + 1; k < list.size(); k++) {
                makeWall(i, j, k); // 벽 3개 세우기
                ans = Math.max(ans, getSafetyArea()); // 안전 영역 최댓값 갱신
                removeWall(i, j, k); // 백트래킹 (원상 복구)
             }
          }
       }
       
       bw.write(ans + "");
       bw.flush();
       bw.close();
       br.close();
    }

    static int getSafetyArea() {
       Queue<Node> q = new LinkedList<>();
       boolean[][] visited = new boolean[n][m];
       
       // 초기 바이러스 위치를 큐에 모두 삽입
       for (int i = 0; i < n; i++) {
          for (int j = 0; j < m; j++) {
             if (a[i][j] == 2) {
                q.add(new Node(i, j));
                visited[i][j] = true;
             }
          }
       }

       // BFS를 통한 바이러스 확산 시뮬레이션
       while (!q.isEmpty()) {
          Node node = q.poll();
          for (int i = 0; i < 4; i++) {
             int ny = node.y + dy[i];
             int nx = node.x + dx[i];
             
             if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
             // 빈 칸(0)인 곳으로만 바이러스가 퍼질 수 있음
             if (a[ny][nx] != 0 || visited[ny][nx])
                continue;
                
             q.add(new Node(ny, nx));
             visited[ny][nx] = true;
          }
       }

       // 안전 영역(바이러스가 퍼지지 않은 빈 칸) 계산
       int cnt = 0;
       for (int i = 0; i < n; i++) {
          for (int j = 0; j < m; j++) {
             if (a[i][j] == 0 && !visited[i][j]) {
                cnt++;
             }
          }
       }

       return cnt;
    }

    static void makeWall(int i, int j, int k) {
       Node n1 = list.get(i);
       Node n2 = list.get(j);
       Node n3 = list.get(k);

       a[n1.y][n1.x] = 1;
       a[n2.y][n2.x] = 1;
       a[n3.y][n3.x] = 1;
    }

    static void removeWall(int i, int j, int k) {
       Node n1 = list.get(i);
       Node n2 = list.get(j);
       Node n3 = list.get(k);

       a[n1.y][n1.x] = 0;
       a[n2.y][n2.x] = 0;
       a[n3.y][n3.x] = 0;
    }

    static class Node {
       int y, x;

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

알고리즘 분류

그래프 탐색, 너비 우선 탐색 (BFS), 브루트포스 알고리즘 (완전탐색)