[오늘의 백준 문제] 15683번 감시 - 백트래킹

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

 

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

 

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

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

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

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

 

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다.

위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

 

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

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

6 6
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

 

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.

15

첫째 줄에 사각 지대의 최소 크기를 출력한다.

 

 

---

✅ 아이디어

• 이 문제는 백트래킹(DFS) + 완전 탐색을 이용해야 한다.
• 모든 CCTV의 회전 방향을 고려하여 사각지대의 최소 크기를 찾는 것이 목표
• 각 CCTV마다 가능한 감시 방향 조합을 미리 정의한다. → 3차원 배열
  
  • CCTV는 최대 8개이므로, 가능한 모든 경우의 수를 탐색해도 된다.
• 맵을 입력받을 때, CCTV의 좌표와 종류를 리스트에 저장해둔다.
• 백트래킹을 통해 CCTV 회전 경우의 수 탐색
  • CCTV의 감시 방향을 하나씩 설정하면서 재귀적으로 탐색한다.
  • 모든 CCTV의 방향이 정해지면, 감시되는 영역을 확인하여 사각지대를 계산한다.
• 모든 경우를 시도하면서 최소 사각지대를 갱신한다.

 

✅ 시간 복잡도

• 최대 CCTV 개수 = 8
• 각 CCTV당 최대 4가지 방향
• 4⁸ = 65536 → 가능!

 

✅ CCTV 방향 정의

1번	4가지	(→), (↓), (←), (↑)
2번	2가지	(→ ←), (↓ ↑)
3번	4가지	(→ ↓), (↓ ←), (← ↑), (↑ →)
4번	4가지	(→ ↓ ←), (↓ ← ↑), (← ↑ →), (↑ → ↓)
5번	1가지	(→ ↓ ← ↑)

 

 

✅ 코드 구현

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

public class Main {
    static int N, M;
    static int[][] map;
    static List<CCTV> cctvs = new ArrayList<>();
    static int minBlindSpots = Integer.MAX_VALUE;

    // CCTV 방향 설정 (→ ↓ ← ↑)
    static int[][] directions = {
            {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };

    // CCTV 별 감시 가능한 방향 (회전 포함)
    static int[][][] cctvDirections = {
            {}, // 0번 (사용 X)
            {{0}, {1}, {2}, {3}}, // 1번
            {{0, 2}, {1, 3}}, // 2번
            {{0, 1}, {1, 2}, {2, 3}, {3, 0}}, // 3번
            {{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}}, // 4번
            {{0, 1, 2, 3}} // 5번
    };

    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());
        map = new int[N][M];

        // 입력 받기 & CCTV 정보 저장
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] >= 1 && map[i][j] <= 5) {
                    cctvs.add(new CCTV(i, j, map[i][j]));
                }
            }
        }

        // 백트래킹을 사용하여 CCTV 방향 설정 및 탐색
        dfs(0, map);
        System.out.println(minBlindSpots);
    }

    // 백트래킹 DFS로 모든 CCTV 배치 탐색
    static void dfs(int depth, int[][] map) {
        if (depth == cctvs.size()) {
            minBlindSpots = Math.min(minBlindSpots, countBlindSpots(map));
            return;
        }

        CCTV cctv = cctvs.get(depth);
        int type = cctv.type;

        // CCTV 종류에 따른 모든 방향 탐색
        for (int[] directions : cctvDirections[type]) { // 2번일 경우: {0, 2}, {1, 3}
            int[][] copiedMap = copyMap(map);
            for (int dir : directions) {
                markSurveillanceArea(copiedMap, cctv.r, cctv.c, dir);
            }
            dfs(depth + 1, copiedMap);
        }
    }

    // 사각지대 개수 카운트
    static int countBlindSpots(int[][] map) {
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) count++;
            }
        }
        return count;
    }

    // 감시 영역 표시
    static void markSurveillanceArea(int[][] map, int r, int c, int dir) {
        int nr = r;
        int nc = c;

        while (true) {
            nr += directions[dir][0];
            nc += directions[dir][1];

            // 범위 초과 또는 벽(6) 만나면 중지
            if (nr < 0 || nc < 0 || nr >= N || nc >= M || map[nr][nc] == 6) break;

            // CCTV가 아니라면 감시 영역으로 표시
            if (map[nr][nc] == 0) {
                map[nr][nc] = -1; // 감시 표시
            }
        }
    }

    // 2차원 배열 복사
    static int[][] copyMap(int[][] original) {
        int[][] copied = new int[N][M];
        for (int i = 0; i < N; i++) {
            copied[i] = original[i].clone();
        }
        return copied;
    }

    // CCTV 위치 정보를 저장하는 클래스
    static class CCTV {
        int r, c, type;

        CCTV(int r, int c, int type) {
            this.r = r;
            this.c = c;
            this.type = type;
        }
    }
}

 

 

---

 

⚠️ 주의점: 배열을 복사할 때 얕은 복사(Shallow Copy) 와 깊은 복사(Deep Copy) 에 주의해야 한다.

 

---

🚨 얕은 복사(Shallow Copy)

int[][] copiedMap = originalMap; // ❌ 이렇게 하면 안 됨

 

위 코드는 배열의 참조(주소)만 복사하는 것이므로, copiedMap을 수정하면 originalMap도 변경된다!

 

---

✅ 깊은 복사(Deep Copy)

static int[][] copyMap(int[][] originalMap) {
    int[][] copiedMap = new int[N][M];
    for (int i = 0; i < N; i++) {
        copiedMap[i] = originalMap[i].clone(); // ✔️ 한 줄씩 복사
    }
    return copiedMap;
}

• clone()을 사용하면 새로운 배열을 생성하여 originalMap과 독립적인 복사가 이루어진다.
• 이를 통해 copiedMap을 변경해도 originalMap에는 영향이 없다.

 

배열을 복사할 때는 반드시 clone()을 사용하여 깊은 복사를 해야 한다!