[BOJ] 15683 감시 - JAVA

📚 Problem

15683 감시

📝 Solution

• 상(↑) - 0, 우(→) - 1, 하(↓) - 2, 좌(←) - 3
  카메라 종류에 따라
  - 1번 : (0), (1), (2), (3) ➡️ 4 가지
  - 2번 : (0, 2), (1, 3) ➡️ 2 가지
  - 3번 : (0, 1), (1, 2), (2, 3), (0, 3) ➡️ 4 가지
  - 4번 : (0, 1, 3), (0, 1, 2), (1, 2, 3), (0, 2, 3) ➡️ 4 가지
  - 5번 : (0, 1, 2, 3) ➡️ 1 가지

    private static void monitoring(Cctv cctv, int dir, int[][] copiedOffice){
        switch (cctv.num){
            case 1:
                if (dir == 0) watch(cctv, 0, copiedOffice);
                else if (dir == 1) watch(cctv, 1, copiedOffice);
                else if (dir == 2) watch(cctv, 2, copiedOffice);
                else if (dir == 3) watch(cctv, 3, copiedOffice);
                break;

• 벽에 부딪히지 않고 범위 내에서 해당하는 방향으로 감시를 했다는 것으로 -1로 바꿔줍니다.
• 만약 감시카메라가 있다면 그냥 지나갑니다.

    private static void watch(Cctv cctv, int dir, int[][] copiedOffice){
        int nx = cctv.x, ny = cctv.y;

        while (true){
            nx += dx[dir];
            ny += dy[dir];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M || copiedOffice[nx][ny] == 6)
                break;

            if(copiedOffice[nx][ny] == 0)
                copiedOffice[nx][ny] = -1;
        }
    }

• cctvDir 라는 배열은 CCTV 개수 크기의 배열로 카메라 마다 가능한 방향의 경우의 수(4가지)를 저장하기 위해 사용합니다.
• CCTV 개수 만큼 DFS를 이용하여 모든 경우의 수를 구하여 사각 지대의 최솟값을 구합니다.

    private static void DFS(int depth){
        if(depth == cctvs.size()){
            int[][] copiedOffice = copyOffice();

            for(int i = 0; i < cctvs.size(); i++)
                monitoring(cctvs.get(i), cctvDir[i], copiedOffice);

            compBlindSpot(copiedOffice);

            return;
        }

        for(int i = 0; i < 4; i++){
            cctvDir[depth] = i;
            DFS(depth + 1);
        }
    }

💻 Code

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

class Cctv{
    int x;
    int y;
    int num;
    public Cctv(int x, int y, int num){
        this.x = x;
        this.y = y;
        this.num = num;
    }
}

public class Main {
    private static int N, M, min = 100;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static int[] cctvDir;
    private static int[][] office;
    private static ArrayList<Cctv> cctvs = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();
        office = new int[N][M];

        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++){
                office[i][j] = scanner.nextInt();
                if(office[i][j] >= 1 && office[i][j] <= 5)
                    cctvs.add(new Cctv(i, j, office[i][j]));
            }
        cctvDir = new int[cctvs.size()];

        DFS(0);

        System.out.println(min);

        scanner.close();
    }

    private static void watch(Cctv cctv, int dir, int[][] copiedOffice){
        int nx = cctv.x, ny = cctv.y;

        while (true){
            nx += dx[dir];
            ny += dy[dir];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M || copiedOffice[nx][ny] == 6)
                break;

            if(copiedOffice[nx][ny] == 0)
                copiedOffice[nx][ny] = -1;
        }
    }

    private static void monitoring(Cctv cctv, int dir, int[][] copiedOffice){
        switch (cctv.num){
            case 1:
                if (dir == 0) watch(cctv, 0, copiedOffice);
                else if (dir == 1) watch(cctv, 1, copiedOffice);
                else if (dir == 2) watch(cctv, 2, copiedOffice);
                else if (dir == 3) watch(cctv, 3, copiedOffice);
                break;
            case 2:
                if (dir == 0 || dir == 2){
                    watch(cctv, 0, copiedOffice);
                    watch(cctv, 2, copiedOffice);
                }
                else if(dir == 1 || dir == 3){
                    watch(cctv, 1, copiedOffice);
                    watch(cctv, 3, copiedOffice);
                }
                break;
            case 3:
                if (dir == 0){
                    watch(cctv, 0, copiedOffice);
                    watch(cctv, 1, copiedOffice);
                }
                else if (dir == 1){
                    watch(cctv, 1, copiedOffice);
                    watch(cctv, 2, copiedOffice);
                }
                else if (dir == 2){
                    watch(cctv, 2, copiedOffice);
                    watch(cctv, 3, copiedOffice);
                }
                else if (dir == 3){
                    watch(cctv, 3, copiedOffice);
                    watch(cctv, 0, copiedOffice);
                }
                break;
            case 4:
                if (dir == 0){
                    watch(cctv, 0, copiedOffice);
                    watch(cctv, 1, copiedOffice);
                    watch(cctv, 3, copiedOffice);
                }
                else if (dir == 1){
                    watch(cctv, 0, copiedOffice);
                    watch(cctv, 1, copiedOffice);
                    watch(cctv, 2, copiedOffice);
                }
                else if (dir == 2){
                    watch(cctv, 1, copiedOffice);
                    watch(cctv, 2, copiedOffice);
                    watch(cctv, 3, copiedOffice);
                }
                else if (dir == 3){
                    watch(cctv, 0, copiedOffice);
                    watch(cctv, 2, copiedOffice);
                    watch(cctv, 3, copiedOffice);
                }
                break;
            case 5:
                watch(cctv, 0, copiedOffice);
                watch(cctv, 1, copiedOffice);
                watch(cctv, 2, copiedOffice);
                watch(cctv, 3, copiedOffice);
                break;
        }
    }

    private static int[][] copyOffice(){
        int[][] tmpOffice = new int[N][M];

        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                tmpOffice[i][j] = office[i][j];

        return tmpOffice;
    }

    private static void compBlindSpot(int[][] tmpOffice){
        int cnt = 0;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                if(tmpOffice[i][j] == 0)
                    cnt++;
        if(cnt < min)
            min = cnt;
    }

    private static void DFS(int depth){
        if(depth == cctvs.size()){
            int[][] copiedOffice = copyOffice();

            for(int i = 0; i < cctvs.size(); i++)
                monitoring(cctvs.get(i), cctvDir[i], copiedOffice);

            compBlindSpot(copiedOffice);

            return;
        }

        for(int i = 0; i < 4; i++){
            cctvDir[depth] = i;
            DFS(depth + 1);
        }
    }
}