[Boj]: 감시 LINK

문제

사무실의 위치를 나태나는 격자안에 cctv가 설치되어 있고 cctv에 의해 감시 받지 않는 구역의 크기의 최솟 값을 구하는 문제.(단, cctv는 90도 회전이 가능하고 벽을 지날 수 없다.)

요약설명

각 cctv를 회전하여 감시를 할 때 0의 개수를 최소로 나온 값을 출력하는 것이다.

풀이

각 cctv의 회전하는 경우의 수는 cctv번호에 따라 다르다.
1번은 4가지 가능하고, 2번 2가지,3번 4가지,4번 4가지,5번 1가지 이다.

경우의 수를 뽑기 위해 dfs를 이용하여 해당 cctv를 뽑고 회전을 한방향씩 해가면서 씨시티비에 개수만큼 뽑을 때 0의 개수를 count하면 된다.

입력예제

4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

0 0 # 0 0 0
0 0 # 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

cnt : 20

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 # 6 0
0 0 0 0 0 0

cnt : 21

0 0 0 0 0 0
0 0 0 0 0 0
# # 1 0 6 0
0 0 0 0 0 0
cnt : 20

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 # 0 0 0
cnt : 21

최솟값(20,21,20,21)

답 20;

Code

package Thur_Sunday_aWeek_Al.Random;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Surveillance {
    static class Node {
        int y, x, number;

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

    static int n, m, ans = Integer.MAX_VALUE;
    static int[][] office;
    static ArrayList<Node> cctv;

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

        n = sc.nextInt();
        m = sc.nextInt();
        office = new int[n][m];
        cctv = new ArrayList<>();
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            String str[] = sc.nextLine().split(" ");
            for (int j = 0; j < m; j++) {
                office[i][j] = Integer.parseInt(str[j]);
                if (office[i][j] > 0 && office[i][j] <= 5)
                    cctv.add(new Node(i, j, office[i][j]));
            }
        }

        dfs(0, office);
        System.out.println(ans);
    }

    static void dfs(int cctvNumber, int middle_ans[][]) {
        int[][] visited = new int[n][m];
        if (cctvNumber == cctv.size()) {
            // cctv가 아무것도 없음.
            int temp = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (middle_ans[i][j] == 0) {
                        temp++;
                    }
                }
            }
            if (temp < ans) {
                ans = temp;
            }
        } else {
            Node node = cctv.get(cctvNumber);
            int number = node.number;
            int y = node.y;
            int x = node.x;

            switch (number) {
                case 1:
                    // 회전 4가지 방향.
                    for (int i = 0; i < 4; i++) {
                        for (int j = 0; j < n; j++) {
                            visited[j] = Arrays.copyOf(middle_ans[j], m);
                        }
                        detect(visited, y, x, i);
                        dfs(cctvNumber + 1, visited);
                    }
                    break;
                case 2:
                    for (int i = 0; i < 2; i++) {
                        for (int j = 0; j < n; j++) {
                            visited[j] = Arrays.copyOf(middle_ans[j], m);
                        }
                        detect(visited, y, x, i);
                        detect(visited, y, x, i + 2);
                        dfs(cctvNumber + 1, visited);
                    }
                    break;
                case 3:
                    for (int i = 0; i < 4; i++) {
                        for (int j = 0; j < n; j++) {
                            visited[j] = Arrays.copyOf(middle_ans[j], m);
                        }
                        detect(visited, y, x, i);
                        detect(visited, y, x, (i + 1) % 4);
                        dfs(cctvNumber + 1, visited);
                    }
                    break;
                case 4:
                    for (int i = 0; i < 4; i++) {
                        for (int j = 0; j < n; j++) {
                            visited[j] = Arrays.copyOf(middle_ans[j], m);
                        }
                        detect(visited, y, x, i);
                        detect(visited, y, x, (i + 1) % 4);
                        detect(visited, y, x, (i + 2) % 4);
                        dfs(cctvNumber + 1, visited);
                    }
                    break;
                case 5:
                    for (int j = 0; j < n; j++) {
                        visited[j] = Arrays.copyOf(middle_ans[j], m);
                    }
                    detect(visited, y, x, 0);
                    detect(visited, y, x, 1);
                    detect(visited, y, x, 2);
                    detect(visited, y, x, 3);
                    dfs(cctvNumber + 1, visited);
                    break;
            }
        }
    }

    static void detect(int[][] visited, int y, int x, int direction) {
        // 6일때 벽.
        switch (direction) {
            case 0: // 왼쪽 <--
                for (int k = x; k >= 0; k--) {
                    if (office[y][k] == 6) {
                        break;
                    }
                    visited[y][k] = 7;
                }
                break;

            case 1: // 위쪽
                for (int k = y; k >= 0; k--) {
                    if (office[k][x] == 6) {
                        break;
                    }
                    visited[k][x] = 7;
                }
                break;
            case 2: // 오른쪽
                for (int k = x; k < m; k++) {
                    if (office[y][k] == 6) {
                        break;
                    }
                    visited[y][k] = 7;
                }
                break;
            case 3: // 아래
                for (int k = y; k < n; k++) {
                    if (office[k][x] == 6) {
                        break;
                    }
                    visited[k][x] = 7;
                }
                break;
        }
    }
}