[백준 JAVA] 15683 : 감시

[백준] 15683 : 감시 : https://www.acmicpc.net/problem/15683

---

문제 조건 정리

 

1. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다.

사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

 

2. CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

3. 사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

 

---

입력

 

1. 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
2. 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
3. CCTV의 최대 개수는 8개를 넘지 않는다.

---

문제를 풀기 전

 

1. 벽의 위치를 따로 저장해서 가시영역을 확인할 때, 사용해야할지 고민했다.
   사무실의 최대 크기가 8*8이라서 하지 않음
   겹치는 가시영역 처리도 번거로움
2. 2차원 배열에서 이동하며 인덱스를 변경시키는 것이 맞다고 생각했다.

---

코드

 

package baekJoon;

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

public class BJ15683 {

    static class CCTV {
        // 행, 열, cctv 종류
        int row, col, type;

        public CCTV(int row, int col, int type) {
            this.row = row;
            this.col = col;
            this.type = type;
        }
    }

    static List<CCTV> cctvs;
    static int minBlindSpot = Integer.MAX_VALUE; // 정답 (사각지대 최소값)
    static int n, m;

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

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

        n = Integer.parseInt(stringTokenizer.nextToken());
        m = Integer.parseInt(stringTokenizer.nextToken());

        int[][] map = new int[n][m];
        cctvs = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                if (0 < map[i][j] && map[i][j] < 6) {
                    cctvs.add(new CCTV(i, j, map[i][j]));
                }
            }
        }

        // 0 ~ cctv 개수를 dfs, 백트래킹
        dfs(0, map);

        // 정답 출력
        System.out.println(minBlindSpot);

    }

    private static void dfs(int depth, int[][] currMap) {
        // cctvs 마지막 인덱스 = cctvs.size - 1
        if (depth == cctvs.size()) {
            minBlindSpot = Math.min(minBlindSpot, countBlindSpots(currMap));
            return;
        }

        // 현재 깊이에 맞는 cctv
        CCTV curr = cctvs.get(depth);

        // 0, 90, 180, 270
        int rotationCount = 4;

        // 타입이 2라면, 좌우/상하 (2종류)
        if (curr.type == 2) {
            rotationCount = 2;
        }
        // 타입이 5라면, 상하좌우 (1종류)
        else if (curr.type == 5) {
            rotationCount = 1;
        }

        for (int rotation = 0; rotation < rotationCount; rotation++) {
            int[][] newMap = copyMap(currMap);
            simulate(newMap, curr.row, curr.col, curr.type, rotation);
            dfs(depth + 1, newMap);
        }

    }

    private static void simulate(int[][] newMap, int row, int col, int type, int rotation) {
        switch (type) {
            case 1: // 우 || 하 || 좌 || 상
                watch(newMap, row, col, rotation);
                break;
            case 2: // 우좌 || 하상
                watch(newMap, row, col, rotation);
                watch(newMap, row, col, rotation + 2);
                break;
            case 3: // 우하 || 하좌 || 좌상 || 상우
                watch(newMap, row, col, rotation);
                watch(newMap, row, col, (rotation + 1) % 4);
                break;
            case 4: // 우하좌 || 하좌상 || 좌상우 || 상우하
                watch(newMap, row, col, rotation);
                watch(newMap, row, col, (rotation + 1) % 4);
                watch(newMap, row, col, (rotation + 2) % 4);
                break;
            case 5: // 상하좌우
                watch(newMap, row, col, 0);
                watch(newMap, row, col, 1);
                watch(newMap, row, col, 2);
                watch(newMap, row, col, 3);
                break;
        }
    }

    private static void watch(int[][] map, int row, int col, int rotation) {
        while (true) {
//            rotation
//            0 -> row + 1
//            1 -> col + 1
//            2 -> row - 1
//            3 -> col - 1
            row += dx[rotation];
            col += dy[rotation];

            if (row < 0 || row >= n || col < 0 || col >= m || map[row][col] == 6) break;

            if (map[row][col] == 0) {
                map[row][col] = -1; // 감시 영역 표시, currMap 이 아닌 newMap
            }
        }
    }


    // 기존 맵 복사
    private static int[][] copyMap(int[][] oldMap) {
        int[][] newMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            System.arraycopy(oldMap[i], 0, newMap[i], 0, m);
        }
        return newMap;
    }

    // 사각지대 탐색
    private static int countBlindSpots(int[][] map) {
        int count = 0;
        for (int[] row : map) {
            for (int cell : row) {
                if (cell == 0) count++;
            }
        }
        return count;
    }
}

 

---

문제를 풀고 난 후

 

백트래킹을 포함한 시뮬레이션 문제인 것을 감안한다면, 상당히 친절하고 풀이 방법을 떠올리기 간단했던 문제였다.

시간 복잡도를 줄이는 방법도 떠올리기 어렵지 않았다.