[BOJ] 14502. 연구소 - Combination&BFS

[BOJ] 14502. 연구소 - Combination&BFS

제출일 : 2019-10-16

문제 풀이 시간 : 1H 30M

난이도 : ★★★

Problem

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

Input

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

Output

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

Example

input

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

output

27

Solution & Inpression

시뮬레이션 문제

처음 문제를 읽었을때 BFS를 이용하여 바이러스를 퍼트리는 문제임은 쉽게 이해할 수있다.

하지만 벽을 세울때 어떻게 새워야 하는지 오랫동안 고민 하다. 방법을 모르겠어서 계산기를 키고 최악의 경우를 계산하기 시작했다

최악의 경우 8x8 크기의 2차원 배열에 바이러스가 2개만 존재하며 벽은 하나도 없을때 벽을 세울수 있는 경우의 수라고 생각을 했고 이 경우는 $_{62}C_3=37,820$으로 나오기때문에 조합을 이용하여 완전 탐색을 하면 되겠다라고 생각을 정리하고 문제를 풀기 시작했다.

문제를 풀며 직면했던 문제는

1. 오랜만에 구현해본 조합
2. 2차원 배열의 깊은 복사

정도로 쉽게 해결할 수 있었다.

Code

언어 : JAVA

메모리 : 134,316 kb

실행시간 : 548 ms

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, max;
    static int[][] map, copyMap;
    static boolean[] visit;
    static ArrayList<int[]> virus, wall;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];
        virus = new ArrayList<>();
        wall = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 0) {
                    wall.add(new int[] { i, j });
                } else if (map[i][j] == 2) {
                    virus.add(new int[] { i, j });
                }
            }
        }
        max = Integer.MIN_VALUE;
        visit = new boolean[wall.size()];
        copyMap = new int[N][M];
        combination(wall.size(), 3, 0, 0);
        System.out.println(max);
    }

    static void combination(int n, int r, int depth, int start) {
        if (r == depth) {
            for(int i = 0; i<N; i++)
                copyMap[i] = map[i].clone();
            for (int i = 0; i < n; i++) {
                if (visit[i]) {
                    copyMap[wall.get(i)[0]][wall.get(i)[1]] = 1;
                }
            }
            BFS();
            return;
        }
        for (int i = start; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                combination(n, r, depth + 1, i);
                visit[i] = false;
            }
        }
    }

    private static void BFS() {
        int[] dr = { -1, 1, 0, 0 };
        int[] dc = { 0, 0, 1, -1 };
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < virus.size(); i++) {
            q.offer(virus.get(i));
        }
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int r = cur[0] + dr[k];
                int c = cur[1] + dc[k];

                if (range(r, c)) { // 범위 안
                    if (copyMap[r][c] == 0) {
                        copyMap[r][c] = 2;
                        q.offer(new int[] { r, c });
                    }
                }
            }
        } // end of while
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copyMap[i][j] == 0)
                    count++;
            }
        }
        if (max < count)
            max = count;
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < M)
            return true;
        return false;
    }

}