[Algo] 백준 15683 감시 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/15683

메모리 : 56844KB

시간 : 344ms

언어 : Java 11

---

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.concurrent.BrokenBarrierException;

class Main {
    static int[][] board;
    static int N, M;
    static List<Pair> cctvList = new ArrayList<>();
    static int cctvCount;
    static int minCount = Integer.MAX_VALUE;

    static class Pair {
        int x, y, type;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] != 0 && board[i][j] != 6) {
                    cctvList.add(new Pair(i, j, board[i][j]));
                }
            }
        }

        cctvCount = cctvList.size();
        dfs(0, board);
        System.out.println(minCount);
    }

    static void dfs(int index, int[][] map) {
        if (index == cctvCount) {
            int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 0) {
                        count++;
                    }
                }
            }
            minCount = Math.min(minCount, count);
            return;
        }

        Pair cctv = cctvList.get(index);
        int x = cctv.x;
        int y = cctv.y;
        int type = cctv.type;

        int[][] newMap;
        switch (type) {
            case 1:
                for (int i = 0; i < 4; i++) {
                    newMap = copyMap(map);
                    watch(newMap, x, y, i);
                    dfs(index + 1, newMap);
                }
                break;
            case 2:
                for (int i = 0; i < 2; i++) {
                    newMap = copyMap(map);
                    watch(newMap, x, y, i);
                    watch(newMap, x, y, i + 2);
                    dfs(index + 1, newMap);
                }
                break;
            case 3:
                for (int i = 0; i < 4; i++) {
                    newMap = copyMap(map);
                    watch(newMap, x, y, i);
                    watch(newMap, x, y, (i + 1) % 4);
                    dfs(index + 1, newMap);
                }
                break;
            case 4:
                for (int i = 0; i < 4; i++) {
                    newMap = copyMap(map);
                    watch(newMap, x, y, i);
                    watch(newMap, x, y, (i + 1) % 4);
                    watch(newMap, x, y, (i + 2) % 4);
                    dfs(index + 1, newMap);
                }
                break;
            case 5:
                newMap = copyMap(map);
                watch(newMap, x, y, 0);
                watch(newMap, x, y, 1);
                watch(newMap, x, y, 2);
                watch(newMap, x, y, 3);
                dfs(index + 1, newMap);
                break;
        }
    }

    static void watch(int[][] map, int x, int y, int dir) {
        int nx = x;
        int ny = y;

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

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

            if (map[nx][ny] == 0) {
                map[nx][ny] = -1;
            }
        }
    }

    static int[][] copyMap(int[][] map) {
        int[][] newMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                newMap[i][j] = map[i][j];
            }
        }
        return newMap;
    }

    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
}

풀이

귀찮은 구현문제ㅜ CCTV를 돌려가면서 사각지대의 개수를 세 주면 된다.