[JAVA] 백준 15683 감시

 

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

문제분석

사무실에 설치된 CCTV의 방향을 적절히 회전시켜 사각지대의 최소 개수를 구하는 문제로, 각 CCTV가 가질 수 있는 방향 조합을 모두 탐색해야 하는 완전탐색(백트래킹) 문제이다. 먼저 입력을 통해 사무실의 지도와 CCTV의 위치를 저장하고, CCTV의 종류별로 가능한 감시 방향을 미리 배열로 정의한 뒤 DFS를 이용하여 각 CCTV의 방향 조합을 하나씩 선택해 나간다. 탐색 과정에서는 현재 상태의 지도를 복사한 뒤 선택한 방향으로 감시 범위를 표시하고 다음 CCTV로 재귀적으로 진행하며, 모든 CCTV의 방향이 결정된 경우에는 남아 있는 빈 칸(값이 0인 칸)을 계산하여 사각지대의 최소값을 갱신한다. 이때 감시는 지정된 방향으로 벽(6)을 만날 때까지 직선으로 진행되며, 다른 CCTV는 감시를 막지 않고 통과할 수 있다는 점에 주의해야 한다. 

 

이 문제에서 가장 어려운 부분은 "구현"이다. 

코드

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

public class Main {
    static int[][][] dir = {
            {}, // dummy
            { { 0 }, { 1 }, { 2 }, { 3 } }, // 1번 CCTV
            { { 0, 2 }, { 1, 3 } }, // 2번 CCTV
            { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 0 } }, // 3번 CCTV
            { { 0, 1, 2 }, { 1, 2, 3 }, { 2, 3, 0 }, { 3, 0, 1 } }, // 4번 CCTV
            { { 0, 1, 2, 3 } } // 5번 CCTV
    };
    // 0 위, 1 오른, 2 아래, 3 왼
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, 1, 0, -1 };

    static int[][] arr;// 0 빈칸, 6 벽, 1~5 CCTV(90도 회전 가능)
    static int count = Integer.MAX_VALUE; // 안 가려지는 부분 최댓값 저장(CCTV 위치도 포함)
    static ArrayList<int[]> cctv; // cctv 배열
    static int N;
    static int M;

    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()); // 가로 크기
        arr = new int[N][M];
        cctv = new ArrayList<>();

        // 입력받고, cctv의 경우 따로 추가
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int n = Integer.parseInt(st.nextToken());
                arr[i][j] = n;
                if (n > 0 && n < 6)
                    cctv.add(new int[] { i, j });
            }
        }

        int[][] map = copy(arr); // 백트래킹용 array(복사해서 사용, 사각지대는 0)
        DFS(0, map);
        System.out.println(count);
    }

    // depth: cctv 인덱스. 해당 idx의 cctv를 회전시키는 모든 경우의 수로 배치한 뒤 재귀 DFS.
    static void DFS(int depth, int[][] map) {
        if(depth == cctv.size()){
            count(map);
            return;
        }
        int[] rc = cctv.get(depth);
        // cctv 놓인 row,col
        int row = rc[0];
        int col = rc[1];
        int type = arr[row][col];
        for(int[] dest : dir[type]){
            int[][] cloneMap = copy(map);
            for(int d: dest){
                watch(row,col,d,cloneMap);
            }
            DFS(depth + 1, cloneMap);
        }

    }

    // map 복사해서 사용 -> 백트래킹 시 복원 안해도 되게끔
    static int[][] copy(int[][] map) {
        int[][] cloneMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            cloneMap[i] = map[i].clone();
        }
        return cloneMap;
    }

    // map -1은 감시중인 지역
    static void watch(int r, int c, int d, int[][] map) {
        while (true) {
            r += dr[d];
            c += dc[d];
            if (r < 0 || c < 0 || r >= N || c >= M)
                break;
            if (arr[r][c] == 6)
                break;
            if (map[r][c] == 0)
                map[r][c] = -1;
        }
    }

    static void count(int[][] map) {
        int n = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    n += 1;
                }
            }
        }
        count = Math.min(count,n);
    }

}