[BOJ] 17142. 연구소3 - Combination & BFS

[BOJ] 17142. 연구소3 - Combination & BFS

제출일 : 2019-10-17

문제 풀이 시간 : 2H

난이도 : ★★★★

Problem

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

Input

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

Output

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

Example

input

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

output

4

Solution & Inpression

시뮬레이션 문제

연구소 1을 푼지 하루도 되지 않았을때 풀기 시작한 문제 이번에도 역시 모든경우의 조합을 구해 완전탐색을 진행하여 문제를 풀었다.

처음 모든 테스트케이스를 맞추고 제출하였을때 채점이 99%에서 틀렸습니다 메시지가 나왔다.

문제를 천천히 읽었을때 비활성화된 바이러스는 고려하지 않고 빈공간만 탐색하면 된다고 생각을 했고 그렇게 구현을 하였다. 테스트케이스는 맞지만 문제에는 맞지않는 구현이었고 친구의 도움으로 반례를 찾아 풀수 있었다.

찾은 반례는

1x3의 배열에 왼쪽부터 빈공간, 비활성화 된 바이러스, 활성화된 바이러스 순으로 들어있다면 결과는 2가 나와야하지만 -1이 나오게 된다. 따라서 2를 무시하면 안된다는 결론에 이르렀고 2도 역시 탐색의 기준으로 주어줬다.

2를 고려했을때도, 비활성화된 바이러스, 빈공간, 활성화된 바이러스 순이라면 결과는 1이나와야하지만 결과값은 2로 나오게 되었다.

이런 문제를 찾은 뒤에는 0과 2일때 탐색을 하며 0일때만 시간을 갱신해주는 방법으로 문제를 해결했다.

Code

언어 : JAVA

메모리 : 51,032 kb

실행시간 : 376 ms

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

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

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

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

        map = new int[N][N];
        copyMap = new int[N][N];
        virus = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 2)
                    virus.add(new int[] { i, j });
            }
        }
        ans = Integer.MAX_VALUE;
        visit = new boolean[virus.size()];
        combination(virus.size(), M, 0, 0);

        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }// end of main

    static void combination(int n, int r, int start, int depth) {
        if (r == depth) {

            BFS();
            return;
        }
        for (int i = start; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                combination(n, r, i, depth + 1);
                visit[i] = false;
            }
        }
    }

    private static void BFS() {

        for (int i = 0; i < N; i++) {
            copyMap[i] = map[i].clone();
        }

        int[] dr = { 1, -1, 0, 0 };
        int[] dc = { 0, 0, 1, -1 };
        int time = 0;
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < visit.length; i++) {
            if (visit[i]) {
                copyMap[virus.get(i)[0]][virus.get(i)[1]] = 3;
                q.offer(new int[] { virus.get(i)[0], virus.get(i)[1], 0 });
            }
        }

        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];
                // 범위 내이고 0과 2일때만 BFS
                if (range(r, c)) {
                    if (copyMap[r][c] == 0) {
                        if (time < cur[2] + 1)
                            time = cur[2] + 1;
                        copyMap[r][c] = 3;
                        q.offer(new int[] { r, c, cur[2] + 1 });
                    } else if (copyMap[r][c] == 2) {
                        copyMap[r][c] = 3;
                        q.offer(new int[] { r, c, cur[2] + 1 });
                    }
                }
            }

        } // end of while

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (copyMap[i][j] == 0)
                    return;
            }
        }

        if (ans > time)
            ans = time;

    }

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

}// end of Class