[Java] 감시 15683

package 백준.자바.감시_15683;

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

public class Main {
    static final int MAX_N = 8;
    static final int MAX_M = 8;
    
    // val은 현재 사각지대의 개수
    static int N, M, val;
    
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int[][] map = new int[MAX_N][MAX_M];
    static int[][][] directions = {
            // 상 하 좌 우
            {},
            {{0}, {1}, {2}, {3}}, // 1번 CCTV : (상), (하), (좌), (우)
            {{0, 1}, {2, 3}}, // 2번 CCTV : (상 하), (좌, 우)
            {{0, 3}, {3, 1}, {1, 2}, {2, 0}}, // 3번 CCTV : (상, 우), (우, 하), (하, 좌), (좌, 상)
            {{0, 1, 2}, {0, 1, 3}, {2, 3, 0}, {2, 3, 1}}, // 4번 CCTV : (상, 하, 좌), (상, 하, 우), (좌, 우, 상), (좌, 우, 하)
            {{0, 1, 2, 3}} // 5번 CCTV : (상, 하, 좌, 우)
    };
    
    static Stack<Pair> s = new Stack<>();
    static ArrayList<Cctv> cctvList = new ArrayList<>();
    
    static class Pair{
        int row;
        int col;

        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static class Cctv{
        int row;
        int col;
        int type;

        public Cctv(int row, int col, int type) {
            this.row = row;
            this.col = col;
            this.type = type;
        }
    }

    // 좌표와 방향이 주어지면, 해당 방향으로 CCTV를 비추는 함수
    // 비춘 칸 수를 반환
    static int check(int row, int col, int dir){
        // 상 하 좌 우 (0, 1, 2, 3)
        row += dx[dir];
        col += dy[dir];
        
        // 해당 방향으로 비추게 된 칸의 개수
        int count = 0;
        
        // 배열 밖으로 나가거나, 6(벽)을 만날 때까지 반복
        while(row < N && col < M && row >= 0 && col >= 0 && map[row][col] != 6){
            
            if(map[row][col] == 0){
                count += 1;
                map[row][col] = -1;
                s.add(new Pair(row, col));
            }
            row += dx[dir];
            col += dy[dir];
        }
        return count;
    }


    static int min = Integer.MAX_VALUE;

    static void dfs(int index){
        if(index >= cctvList.size()) {
            min = Math.min(val, min);
            return;
        }


        Cctv cctv = cctvList.get(index);

        // type에 따라 전체 반복 횟수 결정
        for(int dir = 0; dir < directions[cctv.type].length; dir++) {

            int count = 0;

            for(int k = 0; k < directions[cctv.type][0].length; k++) {
                count += check(cctv.row, cctv.col, directions[cctv.type][dir][k]);
            }

            val -= count;
            dfs(index + 1);

            for(int i = 0; i < count; i++){
                Pair p = s.pop();
                map[p.row][p.col] = 0;
                val += 1;
            }
        }
    }


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

        val = N * M;

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                int v = Integer.parseInt(st.nextToken());
                if(v != 0){
                    val -= 1;
                    if(v != 6){
                        cctvList.add(new Cctv(i, j, v));
                    }
                }
                map[i][j] = v;
            }
        }

        dfs(0);

        System.out.println(min);


    }
}

 

풀이 아이디어

 

전처리

1. 각 CCTV가 바라볼 수 있는 경우의 수를 3차원 배열로 저장한다(directions)

2. CCTV 객체의 정보(row, col, dir)을 담는 클래스를 만들고, 이를 배열로 사용하는 ArrayList를 생성하여 CCTV의 정보를 보관한다.

 

풀이

1. 재귀함수를 이용하여, ArrayList의 index를 1씩 증가시키며 모든 CCTV를 순차적으로 조회한다.

2. CCTV의 Type에 따라 directions 배열을 활용하여 map을 업데이트한다.

3. 다시 되돌리는 경우에는 stack을 활용한다.

4. 마지막 CCTV 조회 이후 사각지대의 개수의 최솟 값을 저장한다.