[백준] 15683* - 감시 (골드 3)

https://www.acmicpc.net/problem/15683

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    static int min = Integer.MAX_VALUE;
    static int[][] room;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {-1, 0,1,0}; // 상,우,하,좌

    static ArrayList<cctv> c = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        room = new int[n][m];
        ArrayList<cctv> five = new ArrayList<>();
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                room[i][j] = Integer.parseInt(st.nextToken());
                if(room[i][j]==5) five.add(new cctv(i,j,5));
                else if(room[i][j]!=0) c.add(new cctv(i,j,room[i][j]));
            }
        }

        //  0은 빈 칸, 6은 벽, 1~5는 CCTV
        // 1 - 한 쪽, 2 - 좌,우, 3- 직각, 4-좌,우,앞, 5-+
        // 5는 맵에 # 표시하기
        for(cctv f : five){
            watch(room, f.i, f.j, 0);
            watch(room, f.i, f.j, 1);
            watch(room, f.i, f.j, 2);
            watch(room, f.i, f.j, 3);
        }

        // 방향
        // cctv 검사
        dfs(room,0);
        // 0 개수 파악 -> 최솟값 출력
        System.out.println(min);
    }
    static class cctv{
        int i,j,type;
        public cctv(int i, int j, int type){
            this.i=i; this.j=j; this.type=type;
        }
    }
    // cctv 검사
    static void watch(int[][] map, int r, int c, int dir){
        int nx =r; int ny = c;

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

            if(nx<0||nx>=n||ny<0||ny>=m||map[nx][ny] == 6) break;
            if(map[nx][ny]==0) map[nx][ny] = 7;
        }
    }
    // 방향 선택 함수
    static void dfs(int[][] map, int idx){
        if(idx == c.size()){
            min = Math.min(min, count(map));
            return;
        }

        cctv cur = c.get(idx);
        int x = cur.i; int y=cur.j; int type = cur.type;

        int rotate = 4;
        if(type==2) rotate=2;

        for(int dir=0;dir<rotate;dir++){
            int[][] cp = copyMap(map);

            switch (type){
                case 1:
                    watch(cp, x,y,dir);
                    break;
                case 2: // 상하 or 좌우
                    watch(cp, x,y,dir);
                    watch(cp, x,y,dir+2);
                    break;
                case 3:
                    watch(cp, x,y,dir);
                    watch(cp, x,y,(dir+1)%4);
                    break;
                case 4:
                    watch(cp, x,y,dir);
                    watch(cp, x,y,(dir+1)%4);
                    watch(cp, x,y,(dir+3)%4);
                    break;
            }

            dfs(cp, idx+1);
        }
    }

    // 빈칸 개수 세기
    static int count(int[][] map){
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    count++;
                }
            }
        }
        return count;
    }

    static int[][] copyMap(int[][] map){
        int[][] cp = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cp[i][j] = map[i][j];
            }
        }
        return cp;
    }
}

=> 시간 초과