링크

감시

문제

풀이

푸는데 시간이 많이 걸렸다.
정답률이 높은 것을 보니 내가 구현문제를 잘 못푸는 것 같다.
완탐으로 하면 시간초과 날 줄 알았는데 완탐으로 푸는 문제였다.
dfs를 통해 방향을 완탐한 뒤 cctv의 타입에 따라 방향을 선정하여 사각지대를 찾았다.

코드

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

class CCTV{
    int kind;
    int x;
    int y;

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

}

//14889
public class Algorithm {
    public static int[][] matrix = null;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};
    public static List<Integer> list = new ArrayList<>();
    public static int result = Integer.MAX_VALUE;
    public static List<CCTV> cctvList = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        matrix = new int[n][m];
        for(int i=0;i<n;i++){
            arr = br.readLine().split(" ");

            for(int j=0;j<arr.length;j++){
                matrix[i][j] = Integer.parseInt(arr[j]);

                if(matrix[i][j] != 0 && matrix[i][j] != 6){
                    cctvList.add(new CCTV(matrix[i][j], i, j));
                }
            }
        }


        dfs(0);
        System.out.println(result);

    }

    public static void dfs(int dept){
        if(dept == cctvList.size()){
            int[][] copyMap = new int[matrix.length][matrix[0].length];
            for(int i=0;i<matrix.length;i++){
                for(int j=0;j<matrix[0].length;j++){
                    copyMap[i][j] = matrix[i][j];
                }
            }

            cctv(copyMap);
            area(copyMap);

            return;
        }

        for(int i=0;i<4;i++){
            list.add(i);
            dept+=1;
            dfs(dept);
            dept-=1;
            list.remove(list.size() - 1);
        }
    }

    // 상 우 하 좌
    // 0 1 2 3
    public static void cctv(int[][] map){
        for(int i=0;i<cctvList.size();i++){
            CCTV current = cctvList.get(i);
            int direction = list.get(i);

            if(current.kind == 1){
                paint(map, direction, current);
            } else if(current.kind == 2){
                if(direction == 1 || direction == 3){
                    paint(map, 1, current);
                    paint(map, 3, current);
                } else{
                    paint(map, 0, current);
                    paint(map, 2, current);
                }

            } else if(current.kind == 3){
                if(direction + 1 >= 4){
                    paint(map, 0, current);
                    paint(map, direction, current);
                } else{
                    paint(map, direction, current);
                    paint(map, direction+1, current);
                }
            } else if(current.kind == 4){
                for(int j=0;j<4;j++){
                    if(direction == j) continue;
                    paint(map, j, current);
                }
            } else if(current.kind == 5){
                paint(map, 1, current);
                paint(map, 2, current);
                paint(map, 3, current);
                paint(map, 0, current);
            }

        }
    }

    public static void paint(int[][] map, int direction, CCTV cctv){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(cctv.x);
        queue.add(cctv.y);
        //map[cctv.x][cctv.y] = 7;

        while(!queue.isEmpty()){
            int x = queue.poll() + dx[direction];
            int y = queue.poll() + dy[direction];

            if(x >= 0 && y >= 0 && x < map.length && y < map[0].length && map[x][y] != 6){
                queue.add(x);
                queue.add(y);

                if(map[x][y] == 0)
                map[x][y] = 7;
            }
        }
    }

    public static void area(int[][] map){
        int total = 0;

        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                if(map[i][j] == 0){
                    total++;
                }
            }
        }


        result = Math.min(total, result);
    }


}