백준 14592 - 연구소

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

문제풀이

해당 문제에서는 3가지 입력 N, M, 지도 모양이 주어진다.

• N : 세로 크기
• M : 가로 크기
• 지도 정보

지도 내 상태는 3가지 상태가 존재한다.

• 0 : 빈칸
• 1 : 벽
• 2 : 바이러스

알고리즘 실행계획은 다음과 같이 진행한다.

1. 벽을 세운다.
2. 바이러스 확산 시킨다.
3. 바이러스 영역을 확인한다.

이 문제에서는 3가지 벽을 어떻게 세울지가 관건이다. 다행이 지도의 크기는 최대 8*8을 갖고 지도의 벽을 세울 경우의 수는 64C3의 경우의 수를 갖는다. 지도의 벽을 세우는 경우의 수 * 지도 탐색의 시간 복잡도를 계산하면 최대 260만의 시간 복잡도를 갖게 되므로 브루트 포스 방식으로 벽을 세워서 확인해도 충분히 시간내에 해결할 수 있다.

전체 소스 코드

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

public class Main {
    public static int maxValue = 0;
    public static int[] dy = { 1, -1, 0, 0 };
    public static int[] dx = { 0, 0, 1, -1 };

    public static void findVirus(int N, int M, int[][] lab) {
        int count = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (lab[i][j] == 0) {
                    count++;
                }
            }
        }

        if (count > maxValue) {
            maxValue = count;
        }
    }

    public static void bfs(int N, int M, int[][] lab) {
        Queue<int[]> q = new LinkedList();
        boolean[][] check = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (lab[i][j] == 2) {
                    check[i][j] = true;
                    q.add(new int[] { i, j });
                }
            }
        }

        while (!q.isEmpty()) {
            int[] front = q.remove();
            int cntY = front[0];
            int cntX = front[1];

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

                if (0 > ny || ny >= N || 0 > nx || nx >= M) {
                    continue;
                }

                if (lab[ny][nx] == 0 && check[ny][nx] == false) {
                    lab[ny][nx] = 2;
                    check[ny][nx] = true;
                    q.add(new int[] { ny, nx });
                }
            }
        }
    }

    public static void copyLab(int[][] copiedLab, int[][] lab, int N, int M) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copiedLab[i][j] = lab[i][j];
            }
        }
    }

    public static void makeWall(int N, int M, int[][] lab, int depth) {
        if (depth == 3) {
            int[][] copiedLab = new int[N][M];

            copyLab(copiedLab, lab, N, M);
            bfs(N, M, lab);
            findVirus(N, M, lab);
            copyLab(lab, copiedLab, N, M);

            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (lab[i][j] != 0) {
                    continue;
                }
                lab[i][j] = 1;
                makeWall(N, M, lab, depth + 1);
                lab[i][j] = 0;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int N, M;

        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);

        int[][] lab = new int[N][M];

        for (int i = 0; i < N; i++) {
            inputs = br.readLine().split(" ");

            for (int j = 0; j < M; j++) {
                lab[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        makeWall(N, M, lab, 0);

        System.out.println(maxValue);
    }
}