[백준 / Java] 15683 감시

문제

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

---

 

문제 개요

 이문제는 다양한 종류의 CCTV를 이용해 사무실 공간 내의 사각지대(감시되지 않는 영역)를 최소화하는 시뮬레이션 문제입니다.
각 CCTV는 감시 가능한 방향이 정해져 있으며, 회전을 통해 방향을 설정할 수 있습니다. CCTV는 벽을 넘을 수 없지만 다른 CCTV는 통과할 수 있으며, 모든 CCTV의 방향을 적절히 정해 전체 사무실에서 감시되지 않는 빈 칸(0)의 개수를 최소화하는 것이 목표입니다.

 

접근 방법

1. 문제 분석 및 모델링
   • 사무실은 2차원 배열 map로 표현됩니다.
   • CCTV는 종류(1~5번)에 따라 감시할 수 있는 방향이 다르며, 이에 따라 각각 가능한 방향 조합(monitor)을 미리 정의해 두었습니다.
   • 벽(6)은 감시를 막고, CCTV는 감시할 수 있는 공간에 영향을 주지 않습니다.
2. CCTV 위치 수집
   • 입력을 처리하면서 CCTV의 좌표와 종류를 리스트(list)에 저장합니다.
3. 완전 탐색(백트래킹)
   • bt(idx) 함수로 각 CCTV마다 가능한 모든 방향 조합을 재귀적으로 탐색합니다.
   • 현재 CCTV가 특정 방향을 감시하도록 설정한 뒤 다음 CCTV로 넘어가며, 모든 CCTV의 방향을 결정한 경우 감시 후 사각지대를 계산합니다.
   • 각 경우마다 맵을 복사(copy())하여 상태를 보존하고, 백트래킹 후 원래 상태로 되돌립니다.
4. 감시 구현
   • 감시(watch)는 CCTV 위치에서 특정 방향으로 쭉 이동하며, 벽(6)이나 범위 밖으로 나가기 전까지 감시할 수 있습니다.
   • 감시된 칸은 -1로 마킹합니다.

 

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

public class Main {
    //1 = up
    //2 = right
    //3 = down
    //4 = left
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    static int[][][] monitor = {
            {}, // 0번은 없음
            {   // 1번 CCTV → 한 방향
                    {0}, {1}, {2}, {3}  // 상, 우, 하, 좌
            },
            {   // 2번 CCTV → 두 방향 (반대 방향)
                    {0, 2}, // 상, 하
                    {1, 3}  // 우, 좌
            },
            {   // 3번 CCTV → 두 방향 (직각)
                    {0, 1}, // 상, 우
                    {1, 2}, // 우, 하
                    {2, 3}, // 하, 좌
                    {3, 0}  // 좌, 상
            },
            {   // 4번 CCTV → 세 방향
                    {0, 1, 2}, // 상, 우, 하
                    {1, 2, 3}, // 우, 하, 좌
                    {2, 3, 0}, // 하, 좌, 상
                    {3, 0, 1}  // 좌, 상, 우
            },
            {   // 5번 CCTV → 네 방향 모두
                    {0, 1, 2, 3} // 상, 우, 하, 좌
            }
    };

    static int[][] map;
    static List<Node> list = new ArrayList<>();
    static int ans = Integer.MAX_VALUE;
    static int R, C;
    public static void main(String[] args) throws IOException {
        init();
        bt(0);
        System.out.println(ans);
    }

    public static void bt(int idx) {
        if(idx == list.size()) {
            ans = Math.min(ans, cal());
            return;
        }
        Node cur = list.get(idx);
        int[][] bucket = copy(map);

        for(int[] arr : monitor[cur.num]) {
            watch(cur.r, cur.c, arr);
            bt(idx + 1);
            map = copy(bucket);
        }
    }

    public static int cal() {
        int cnt = 0;

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

        return cnt;
    }

    public static void watch(int r, int c, int[] arr) {
        for(int n : arr) {
            int nr = r;
            int nc = c;

            while (true) {
                nr += dr[n];
                nc += dc[n];
                if(nr>=0 && nc>=0 && nr<R && nc<C && map[nr][nc]<6) {
                    if(map[nr][nc] == 0) map[nr][nc] = -1;
                } else {
                    break;
                }
            }
        }
    }

    public static int[][] copy(int[][] map) {
        int[][] newOne = new int[R][C];
        for(int i=0; i<R; i++){
            newOne[i] = map[i].clone();
        }
        return newOne;
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new int[R][C];

        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                int n = Integer.parseInt(st.nextToken());
                map[i][j] = n;
                if(n > 0 && n < 6) {
                    list.add(new Node(i, j, n));
                }
            }
        }
    }

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