[Java] 백준 15683번 : 감시

1. 문제

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

15683번: 감시

 

 

2. 풀이과정

백트래킹 문제로, 각 감시카메라마다 가능한 감시 구역을 모두 탐색하며 결과값을 찾는다. N, M의 범위가 작기 때문에 전체탐색을 해도 시간 초과가 나지 않는다.

 

1. 전체 구역, 즉 2차원 배열을 재귀함수 simulation으로 전체 탐색을 한다.

2. 이때 해당 구역에 감시카메라가 있다면, 각 번호별로 탐색할 수 있는 구역을 탐색하고 재귀를 진행한다.

3. 감시하는 구역은 2차원 배열의 값을 -1을 해주어, 해당 구역을 감시하고 있는 감시카메라 수를 표시해준다. 즉, 구역의 값이 0이면 사각지대이고 음수면 감시 중인 구역이다.

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

public class Main {
    static int N, M, map[][], result;
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    public static void simulation(int idx){
        if(idx >= N*M){
            result = Math.min(result, cnt());
            return;
        }

        int i = idx/M;
        int j = idx%M;
        switch (map[i][j]){
            case 1:
                for(int k=0; k<4; k++){
                    go(i, j, k);
                    simulation(idx+1);
                    back(i, j, k);
                }
                break;
            case 2:
                for(int k=0; k<2; k++){
                    go(i, j, k);
                    go(i, j, k+2);
                    simulation(idx+1);
                    back(i, j, k);
                    back(i, j, k+2);
                }
                break;
            case 3:
                for(int k=0; k<4; k++){
                    go(i, j, k);
                    go(i, j, (k+1)%4);
                    simulation(idx+1);
                    back(i, j, k);
                    back(i, j, (k+1)%4);
                }
                break;
            case 4:
                for(int k=0; k<4; k++){
                    for(int z=k+2; z>=k; z--){
                        go(i, j, z%4);
                    }
                    simulation(idx+1);
                    for(int z=k+2; z>=k; z--){
                        back(i, j, z%4);
                    }
                }
                break;
            case 5:
                for(int k=0; k<4; k++){
                    go(i, j, k);
                }
                simulation(idx+1);
                for(int k=0; k<4; k++){
                    back(i, j, k);
                }
                break;
            default:
                simulation(idx+1);
        }


    }

    public static void go(int x, int y, int d){
        while(true){
            x += dx[d];
            y += dy[d];
            if(!check(x, y) || map[x][y]==6){break;}
            if(map[x][y]>0){continue;}
            map[x][y]--;
        }
    }

    public static void back(int x, int y, int d){
        while(true){
            x += dx[d];
            y += dy[d];
            if(!check(x, y) || map[x][y]==6){break;}
            if(map[x][y]>0){continue;}
            map[x][y]++;
        }
    }

    public static int cnt(){
        int res = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j]==0){
                    res++;
                }
            }
        }
        return res;
    }

    public static boolean check(int x, int y){
        if(0<=x && x<N && 0<=y && y<M){ return true;}
        return false;
    }

    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());
        map = new int[N][M];
        result = 999_999_999;

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        simulation(0);
        System.out.println(result);
    }
}

 

 

결과