[백준] 연구소 - Gold 4

[jusung-c]

문제 링크

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

문제 조건

N x M 크기의 연구소는 빈 칸(0), 벽(1), 바이러스(2)로 구성되어 있다.

• (3 ≤ N, M ≤ 8)

바이러스는 상하 좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며 꼭 3개를 다 세워야 한다.

• 초기의 바이러스는 2개 이상 10개 이하이다.

벽을 세운 뒤 얻을 수 있는 안전 영역 크기의 최댓값을 구하라

---

아이디어

정답의 최대치

바이러스가 최소치인 2개일 때 안전 영역의 최대치는 N*M 이하이다.

접근 1) 바이러스에 노출된 지역 확인

바이러스가 주어졌을 때 얼마나 퍼질 수 있는지 확인하는 프로그램을 짜야한다.

격자형 그래프에서 바이러스 정점을 시작점으로 갈 수 있는 위치를 BFS로 탐색하면 바이러스에 노출되는 지역을 확인할 수 있을 것이다. 이제까지는 시작점이 하나인 그래프 탐색을 했지만 이번엔 각 바이러스마다 해줘야 하므로 시작점이 여러 개인 탐색을 해야한다.

굳이 모든 바이러스마다 하나씩 BFS를 진행해주는 것이 아닌 단 한 번의 BFS로 모든 바이러스의 감염 경로를 알 수 있는 것이 Multisource BFS이다.

Multisource BFS 진행

이제까지는 Queue에 시작점 하나만 넣어두고 바로 while문으로 들어갔다면, 이번엔 가능한 모든 시작점들을 Queue에 넣고 시작한다.

어차피 바이러스가 전염시킬 수 있는 범위는 한정되어 있으므로 한 번의 BFS와 동일하기 때문에 시간 복잡도는 O(V+E)가 유지된다. 정점의 개수가 최대 N^2개 이므로 총 O(N^2)의 시간이 소요된다.

    private static void bfs() {
        Queue<Point> que = new LinkedList<>();

        // 모든 바이러스들을 시작점으로 넣기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 방문 배열 초기화
                visit[i][j] = false;

                if (map[i][j] == 2) {
                    que.add(new Point(i, j));
                    visit[i][j] = true;
                }
            }
        }

        // 바이러스 전염 시작
        while (!que.isEmpty()) {
            Point p = que.poll();

            for (int d = 0; d < 4; d++) {
                int nx = p.x + dir[d][0];
                int ny = p.y + dir[d][1];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (map[nx][ny] != 0) continue;
                if (visit[nx][ny]) continue;

                que.add(new Point(nx, ny));
                visit[nx][ny] = true;
            }
        }

        // 전염 완료 후 안전 영역 크기 계산
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 이 때 전염된 구역을 제외하기 위해 방문처리 여부를 확인해줘야 한다.
                if (map[i][j] == 0 && !visit[i][j]) cnt++;
            }
        }

        ans = Math.max(ans, cnt);
    }

접근 2) 벽을 어떻게 세울까? - 완전 탐색으로 보자

세 칸을 막을 수 있는 모든 경우의 수는 얼마나 될까?

벽을 세울 수 있는 빈 공간이 B개라고 가정했을 때 벽 3개를 세워야 하므로 B개중 3개를 선택하는 완전 탐색을 생각할 수 있다.

N의 최댓값은 8이고, N^2은 64이므로 빈 공간은 62개 이하일 것이다.

따라서 빈 공간 중 중복을 허용하지 않고 순서와 상관없이 3개를 골라 세우면 되므로 조합문제이다.

따라서 (N^2 C 3) 만큼의 시간이 걸리기 때문에 완전 탐색으로 진행해도 시간 안 풀이가 가능할 것이다.

    static void dfs(int idx, int selected_cnt) {
        if (selected_cnt == 3) {
            // 바이러스 퍼뜨리기
            bfs();
            return;
        }

        // 더 이상 세울 수 있는 벽이 없는 경우
        if (idx >= space) return;

        // idx에 벽을 세우는 경우
        map[blank[idx].x][blank[idx].y] = 1;
        // 다음 벽 세우러 ㄱㄱ
        dfs(idx + 1, selected_cnt + 1);

        // idx에 벽을 안 세우는 경우
        map[blank[idx].x][blank[idx].y] = 0;
        // 다음 벽 세우러 ㄱㄱ
        dfs(idx + 1, selected_cnt);

    }

---

시간 복잡도

1. 완전 탐색해서 64개의 칸 중 3개를 고르는 시간(조합): 64! / 3!61! = 약 41만
2. BFS로 바이러스를 전파시키는 시간: O(N*M)

N과 M의 최댓값이 8이므로 총 시간복잡도는 O(41만 * 64)로 시간 안 풀이가 가능하다.

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N, M, ans, space;
    static int[][] map;
    static Point[] blank;
    static boolean[][] visit;
    static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static class Point {
        int x, y;

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

    public static void init() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ans = 0;
        space = 0;

        visit = new boolean[N][M];
        map = new int[N][M];
        blank = new Point[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) {
                    blank[space] = new Point(i, j);
                    space++;
                };
            }
        }
    }

    private static void pro() throws IOException {
        dfs(0, 0);

        bw.write(ans + " ");
    }

    static void dfs(int idx, int selected_cnt) {
        if (selected_cnt == 3) {
            // 바이러스 퍼뜨리기
            bfs();
            return;
        }

        // 더 이상 세울 수 있는 벽이 없는 경우
        if (idx >= space) return;

        // idx에 벽을 세우는 경우
        map[blank[idx].x][blank[idx].y] = 1;
        // 다음 벽 세우러 ㄱㄱ
        dfs(idx + 1, selected_cnt + 1);

        // idx에 벽을 안 세우는 경우
        map[blank[idx].x][blank[idx].y] = 0;
        // 다음 벽 세우러 ㄱㄱ
        dfs(idx + 1, selected_cnt);

    }

    private static void bfs() {
        Queue<Point> que = new LinkedList<>();

        // 모든 바이러스들을 시작점으로 넣기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 방문 배열 초기화
                visit[i][j] = false;

                if (map[i][j] == 2) {
                    que.add(new Point(i, j));
                    visit[i][j] = true;
                }
            }
        }

        // 바이러스 전염 시작
        while (!que.isEmpty()) {
            Point p = que.poll();

            for (int d = 0; d < 4; d++) {
                int nx = p.x + dir[d][0];
                int ny = p.y + dir[d][1];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (map[nx][ny] != 0) continue;
                if (visit[nx][ny]) continue;

                que.add(new Point(nx, ny));
                visit[nx][ny] = true;
            }
        }

        // 전염 완료 후 안전 영역 크기 계산
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 이 때 전염된 구역을 제외하기 위해 방문처리 여부를 확인해줘야 한다.
                if (map[i][j] == 0 && !visit[i][j]) cnt++;
            }
        }

        ans = Math.max(ans, cnt);
    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}