문제

풀이

1. cctv들의 위치를 list에 저장
2. 모든 cctv와 각 cctv 번호에 맞게 모든 방향 완전탐색

• check() 함수는 감시 가능 구역 체크
• change() 함수는 # 대신 -1로 표시
• undo() 함수는 백트래킹 -1을 다시 0으로

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n,m,ans;
    static ArrayList<Pos> cctv;
    static int[][] map;
    static int[][] d=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        ans=Integer.MAX_VALUE;
        cctv=new ArrayList<>();
        map=new int[n][m];
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                int a=Integer.parseInt(st.nextToken());
                if(a>=1 && a<=5){
                    cctv.add(new Pos(j,i));
                }
                map[i][j]=a;
            }
        }
        dfs(0);
        System.out.println(ans);
    }

    static void dfs(int idx){
        if(idx==cctv.size()){
            int cnt=0;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(map[i][j]==0)cnt++;
                }
            }
            ans=Math.min(cnt,ans);
            return;
        }
        Pos now=cctv.get(idx);
        int y=now.y;
        int x=now.x;
        Queue<Pos> q=new LinkedList<>();
        Queue<Pos> backQ=new LinkedList<>();
        if(map[y][x]==1){
            for(int i=0;i<4;i++){
                check(q,y,x,i);
                change(q,backQ);
                dfs(idx+1);
                undo(backQ);
            }
        }
        else if(map[y][x]==2){
            check(q,y,x,0);
            check(q,y,x,1);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);

            check(q,y,x,2);
            check(q,y,x,3);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);
        }
        else if(map[y][x]==3){
            check(q,y,x,0);
            check(q,y,x,3);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);

            check(q,y,x,3);
            check(q,y,x,1);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);

            check(q,y,x,1);
            check(q,y,x,2);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);

            check(q,y,x,2);
            check(q,y,x,0);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);
        }
        else if(map[y][x]==4){
            check(q,y,x,0);
            check(q,y,x,2);
            check(q,y,x,3);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);

            check(q,y,x,0);
            check(q,y,x,1);
            check(q,y,x,3);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);

            check(q,y,x,2);
            check(q,y,x,3);
            check(q,y,x,1);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);

            check(q,y,x,0);
            check(q,y,x,1);
            check(q,y,x,2);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);
        }
        else if(map[y][x]==5){
            check(q,y,x,0);
            check(q,y,x,1);
            check(q,y,x,2);
            check(q,y,x,3);
            change(q,backQ);
            dfs(idx+1);
            undo(backQ);
        }
    }

    static void check(Queue<Pos> q,int y,int x,int dir){
        while(true){
            int dy=y+d[dir][0];
            int dx=x+d[dir][1];
            if(dy<0||dx<0||dy>=n||dx>=m)break;
            if(map[dy][dx]==6)break;
            if(map[dy][dx]==0)q.add(new Pos(dx,dy));
            y=dy;
            x=dx;
        }
    }
    static void change(Queue<Pos> q,Queue<Pos> backQ){
        while(!q.isEmpty()){
            Pos now=q.poll();
            map[now.y][now.x]=-1;
            backQ.add(now);
        }
    }

    static void undo(Queue<Pos> backQ){
        while(!backQ.isEmpty()){
            Pos now= backQ.poll();
            map[now.y][now.x]=0;
        }
    }
    static class Pos{
        int x,y;

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

}

#구현