백준 알고리즘 - 감시

CCTV의 종류는 총 5개지만
종류마다 방향의 개수가 정해져있지만,
모두 4방향의 경우가 있다고 가정하고 문제를 접근했다.
물론 5번카메라 같은 경우는 방향이 1가지 이기 때문에 이 요소를 고려하고 짠다면,
불필요한 연산을 하지 않아도 된다.

CCTV의 개수는 8개를 넘지 않는다고 하였다.
이 말은 4의 8제곱의 경우의 수를 넘지 않는다.
DFS를 통해 탐색 후 CCTV가 감시하는 부분을 7로 채운 후
마지막의 0의 개수를 세어서 HashSet에 다가 넣어주었다.
그리고 다시 7로 채운 부분을 0으로 돌려주었다.
이 과정을 모든 경우의 수 만큼 반복했다.
모든 경우의 수를 검사하고 난 후 최소값을 출력해 주도록 짰다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
    private static class CCTV{
        int x;
        int y;
        int type;
        boolean visited[];

        public CCTV(int x, int y, int type) {
            this.x = x;
            this.y = y;
            this.type = type;
            this.visited = new boolean[4];
        }
    }

    private static int[] resultDirections;
    private static int[][] room;
    private static int directions = 4;
    private static int cctvCnt = 0;//cctv 개수
    private static ArrayList<CCTV> allCCTV = new ArrayList<>();

    private static HashSet<Integer> resultZero = new HashSet<>();

    private static int height;
    private static int width;

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

        height = sc.nextInt();
        width = sc.nextInt();

        room = new int[height][width];

        for(int i=0; i<height; i++) {
            for(int j=0; j<width; j++) {
                room[i][j] = sc.nextInt();
                if(room[i][j] == 0 || room[i][j] == 6)
                    continue;
                allCCTV.add(new CCTV(i, j, room[i][j]));
            }
        }


        cctvCnt = allCCTV.size();
        resultDirections = new int[cctvCnt];
        DFS();
        System.out.println(minZeroCnt(resultZero));
    }

    private static void DFS(){
        if (cctvCnt > 0) {
            for (int i = 0; i < directions; i++) {
                CCTV cctv = allCCTV.get(0);
                cctv.visited[i] = true;
                DFS_recursion(0, i);
            }
        } else {
            int zeroCnt = printRoomAndCountZero(room);
            resultZero.add(zeroCnt);
        }
    }

    private static void DFS_recursion(int depth, int direction){
        resultDirections[depth] = direction;
        if (depth == cctvCnt-1) {
            for (int i = 0; i < resultDirections.length; i++){
                CCTV cctv = allCCTV.get(i);
                mark7(cctv.type, resultDirections[i], cctv.x, cctv.y);
            }
            int zeroCnt = printRoomAndCountZero(room);
            resultZero.add(zeroCnt);
            getBack7to0(room);
        } else {
            for (int i = 0; i < directions; i++){
                CCTV cctv = allCCTV.get(depth + 1);
                if (cctv.visited[i])
                    continue;
                cctv.visited[i] = true;
                DFS_recursion(depth + 1, i);
                cctv.visited[i] = false;
            }
        }
    }

    private static int minZeroCnt(HashSet<Integer> set){
        int minVal = 100;
        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            int val = (Integer)iterator.next();
            if(val < minVal)
                minVal = val;
        }
        return minVal;
    }

    private static int printRoomAndCountZero(int[][] arr){
        int cnt = 0;
        for (int i = 0; i < arr.length; i++){
            for (int j = 0; j < arr[i].length; j++){
                if (arr[i][j] == 0)
                    cnt++;
            }
        }
        return cnt;
    }

    private static void getBack7to0(int[][] arr){
        for (int i = 0; i < arr.length; i++){
            for (int j = 0; j < arr[i].length; j++){
                if (arr[i][j] == 7)
                    arr[i][j] = 0;
            }
        }
    }

    private static void mark7(int cctvType, int direction, int x, int y){
        switch (cctvType) {
            case 1:
                switch (direction) {
                    case 0://up
                        mark7Up(x,y);
                        break;
                    case 1://right
                        mark7Right(x,y);
                        break;
                    case 2://down
                        mark7Down(x,y);
                        break;
                    case 3://left
                        mark7Left(x,y);
                        break;
                }
                break;
            case 2:
                switch (direction) {
                    case 0://up
                        mark7Up(x,y);
                        mark7Down(x,y);
                        break;
                    case 1://right
                        mark7Left(x,y);
                        mark7Right(x,y);
                        break;
                    case 2://down
                        mark7Up(x,y);
                        mark7Down(x,y);
                        break;
                    case 3://left
                        mark7Left(x,y);
                        mark7Right(x,y);
                        break;
                }
                break;
            case 3:
                switch (direction) {
                    case 0://up
                        mark7Up(x,y);
                        mark7Right(x,y);
                        break;
                    case 1://right
                        mark7Right(x,y);
                        mark7Down(x,y);
                        break;
                    case 2://down
                        mark7Down(x,y);
                        mark7Left(x,y);
                        break;
                    case 3://left
                        mark7Left(x,y);
                        mark7Up(x,y);
                        break;
                }
                break;
            case 4:
                switch (direction) {
                    case 0://up
                        mark7Left(x,y);
                        mark7Up(x,y);
                        mark7Right(x,y);
                        break;
                    case 1://right
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Down(x,y);
                        break;
                    case 2://down
                        mark7Right(x,y);
                        mark7Down(x,y);
                        mark7Left(x,y);
                        break;
                    case 3://left
                        mark7Down(x,y);
                        mark7Left(x,y);
                        mark7Up(x,y);
                        break;
                }
                break;
            case 5:
                switch (direction) {
                    case 0://up
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Left(x,y);
                        mark7Down(x,y);
                        break;
                    case 1://right
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Left(x,y);
                        mark7Down(x,y);
                        break;
                    case 2://down
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Left(x,y);
                        mark7Down(x,y);
                        break;
                    case 3://left
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Left(x,y);
                        mark7Down(x,y);
                        break;
                }
                break;
        }
    }
    private static void mark7Up(int x, int y) {
        for (int i = x-1; i > -1; i--){
            if(room[i][y] == 6)
                break;
            if(room[i][y] == 1 || room[i][y] == 2 || room[i][y] == 3 || room[i][y] == 4 || room[i][y] == 5)
                continue;
            room[i][y] = 7;
        }
    }
    private static void mark7Right(int x, int y) {
        for (int i = y+1; i < room[x].length; i++){
            if(room[x][i] == 6)
                break;
            if(room[x][i] == 1 || room[x][i] == 2 || room[x][i] == 3 || room[x][i] == 4 || room[x][i] == 5)
                continue;
            room[x][i] = 7;
        }
    }
    private static void mark7Down(int x, int y) {
        for (int i = x+1; i < room.length; i++){
            if(room[i][y] == 6)
                break;
            if(room[i][y] == 1 || room[i][y] == 2 || room[i][y] == 3 || room[i][y] == 4 || room[i][y] == 5)
                continue;
            room[i][y] = 7;
        }
    }
    private static void mark7Left(int x, int y) {
        for (int i = y-1; i > -1; i--){
            if(room[x][i] == 6)
                break;
            if(room[x][i] == 1 || room[x][i] == 2 || room[x][i] == 3 || room[x][i] == 4 || room[x][i] == 5)
                continue;
            room[x][i] = 7;
        }
    }

}