[백준 15683] 감시(Java)

문제 링크 : https://www.acmicpc.net/problem/15683

이 문제는 백트래킹을 이용하여 문제의 조건대로 하나하나 구현해나가면 풀 수 있습니다.

이 문제의 접근 방식은 단순합니다. 각 CCTV 타입 별로 칸을 하나하나씩 읽어나가면서 감지 가능 칸을 체크한 후 체크되어있지 않는 부분을 카운트해서 출력하면 됩니다.

여기서 주의할 점은 체크하는 방법입니다. 만약 두 개의 CCTV가 같은 곳을 감지하고 있다면 한 CCTV가 각도를 변경했을 경우 다른 CCTV가 여전히 감지하고 있기 때문에 감지 범위 내입니다. 따라서 단순이 true false로 처리하면 이 부분이 제대로 카운트되지 않기 때문에 CCTV가 감지할 때마다 감지 카운트를 1씩 증가시켜 감지 카운트가 0일 경우 false로서 처리하는 방식으로 진행하시면 되겠습니다.

다음은 코드입니다.

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

public class Main{

    static int N,M;
    static int[][] req = new int[9][9];
    static int[][] check = new int[9][9];
    static int res = 81;
    static ArrayList<Pair> cctvList = new ArrayList<>();
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};

    static int voidNum(){
        int ans = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(check[i][j]==0) ans++;
            }
        }
        return ans;
    }

    static void move(int y, int x, int dir, boolean isCheck){
        int ny = y;
        int nx = x;

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

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

            if(isCheck) check[ny][nx]++;
            else{
                if(check[ny][nx]>0) check[ny][nx]--;
            }
        }
    }

    static void backtracking(int cnt){
        if(cnt == cctvList.size()){
            int ans = voidNum();
            if(res > ans) res = ans;
            return;
        }

        int y = cctvList.get(cnt).y;
        int x = cctvList.get(cnt).x;

        switch (req[y][x]){
            case 1:
                for(int dir=0;dir<4;dir++){
                    move(y,x,dir,true);
                    backtracking(cnt+1);
                    move(y,x,dir,false);
                }
                break;
            case 2:
                for(int dir=0;dir<2;dir++){
                    move(y,x,dir,true);
                    move(y,x,dir+2,true);
                    backtracking(cnt+1);
                    move(y,x,dir,false);
                    move(y,x,dir+2,false);
                }
                break;
            case 3:
                for(int dir=0;dir<4;dir++){
                    int newDir = dir+1;
                    if(newDir==4) newDir = 0;
                    move(y,x,dir,true);
                    move(y,x,newDir,true);
                    backtracking(cnt+1);
                    move(y,x,dir,false);
                    move(y,x,newDir,false);
                }
                break;
            case 4:
                move(y,x,0,true);
                move(y,x,1,true);
                move(y,x,2,true);
                move(y,x,3,true);
                for(int dir=0;dir<4;dir++){
                    move(y,x,dir,false);
                    backtracking(cnt+1);
                    move(y,x,dir,true);
                }
                move(y,x,0,false);
                move(y,x,1,false);
                move(y,x,2,false);
                move(y,x,3,false);
                break;
            case 5:
                move(y,x,0,true);
                move(y,x,1,true);
                move(y,x,2,true);
                move(y,x,3,true);
                backtracking(cnt+1);
                move(y,x,0,false);
                move(y,x,1,false);
                move(y,x,2,false);
                move(y,x,3,false);
                break;
        }
    }

    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());

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                req[i][j] = Integer.parseInt(st.nextToken());
                if(req[i][j] != 0 && req[i][j] != 6){
                    cctvList.add(new Pair(i,j));
                    check[i][j] = 81;
                }
                else if(req[i][j] == 6) check[i][j] = 81;
            }
        }
        backtracking(0);
        System.out.println(res);
    }
}

class Pair{
    int y;
    int x;

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