[백준] 15683: 감시 - JAVA

in Algorithm on 구현

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

풀이

cctv의 방향을 설정하여 사각지대를 최소로 만들어야 한다.

cctv의 종류는 5가지가 있다.

2번 cctv는 방향을 선택할 수 있는 방법이 2가지, 5번 cctv는 1가지였다.

나머지 cctv는 4방향 모두 선택할 수 있다.

입력받으면서 cctv의 위치를 저장했고, 그들의 방향을 저장할 배열을 만들어 각각 어떤 방향을 선택할지 조합을 만들었다.

조합이 완성되면 그 방향에 맞게 빈칸을 채워가면서 체크했다.

처음에 빈칸(0)의 개수를 세어놓고 빈칸을 몇개나 채웠는지를 세어 빼주면 된다.

메모리: 72084KB

시간: 304ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int N, M, zero, ans;
    static int[][] room, tmp;
    static List<Node> list;
    static int[] direction;

    // 오른쪽부터 시계방향
    static int[][] vector = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

    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());
        room = new int[N][M];
        // 빈칸의 개수를 센다
        zero = 0;
        // cctv의 위치를 저장한다
        list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());
                if (room[i][j] == 0) {
                    zero++;
                } else if (room[i][j] < 6) {
                    list.add(new Node(i, j));
                }
            }
        }

        ans = Integer.MAX_VALUE;
        // cctv의 방향을 저장한다
        direction = new int[list.size()];
        makeDirection(0);

        System.out.println(ans);
    }

    private static void makeDirection(int idx) {
        if (idx == list.size()) {
            // 만들어진 방향 배열을 갖고 체크한다
            check();
            return;
        }

        Node node = list.get(idx);

        // 2번은 2방향, 5번은 1방향, 나머지는 4방향 선택 가능
        direction[idx] = 0;
        makeDirection(idx + 1);

        if (room[node.r][node.c] != 5) {
            direction[idx] = 1;
            makeDirection(idx + 1);
        }

        if (room[node.r][node.c] != 2 && room[node.r][node.c] != 5) {
            direction[idx] = 2;
            makeDirection(idx + 1);
            direction[idx] = 3;
            makeDirection(idx + 1);
        }
    }

    private static void check() {
        tmp = new int[N][M];
        for (int i = 0; i < N; i++) {
            tmp[i] = room[i].clone();
        }

        int cnt = 0;
        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            int num = room[node.r][node.c];
            int dir = direction[i];

            // 방향에 맞게 빈칸을 채운다
            switch (num) {
                case 1:
                    cnt += cctv(dir, node.r, node.c);
                    break;
                case 2:
                    cnt += cctv(dir, node.r, node.c);
                    cnt += cctv(dir + 2, node.r, node.c);
                    break;
                case 3:
                    cnt += cctv(dir, node.r, node.c);
                    cnt += cctv((dir + 1) % 4, node.r, node.c);
                    break;
                case 4:
                    cnt += cctv(dir, node.r, node.c);
                    cnt += cctv((dir + 1) % 4, node.r, node.c);
                    cnt += cctv((dir + 2) % 4, node.r, node.c);
                    break;
                case 5:
                    cnt += cctv(dir, node.r, node.c);
                    cnt += cctv(dir + 1, node.r, node.c);
                    cnt += cctv(dir + 2, node.r, node.c);
                    cnt += cctv(dir + 3, node.r, node.c);
                    break;
            }
        }

        ans = Math.min(ans, zero - cnt);
    }

    private static int cctv(int type, int r, int c) {
        int result = 0;

        int nr = r;
        int nc = c;
        while (true) {
            nr += vector[type][0];
            nc += vector[type][1];

            if (nr < 0 || nc < 0 || nr >= N || nc >= M || tmp[nr][nc] == 6) {
                break;
            }
            if (tmp[nr][nc] == 0 && tmp[nr][nc] != -1) {
                result++;
                tmp[nr][nc] = -1;
            }
        }

        return result;
    }
}