[BOJ/Java] 15683: 감시

문제

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

`N`x`M` 크기의 직사각형의 사무실이 있다.

여기에는 `K`개의 CCTV가 설치되어 있고, CCTV의 종류는 5가지다.

CCTV는 90도 회전시킬 수 있다.

지도에서 0은 빈칸, 1~5는 CCTV의 종류, 6은 벽을 의미한다.

CCTV는 CCTV를 통과할 수 있다.

CCTV의 방향을 적절히 조정해서 최소 사각 지대의 개수를 반환해야 한다.

• 1 ≤ `N`, `M` ≤ 8
• CCTV는 8개를 넘지 않는다.

 

풀이

접근법을 떠올리지 못했다. 추후 다시 풀어볼 것.

알고리즘을 사용하지 않고 구현으로 해결해보려 했으나, 코드가 너무 복잡해지는 바람에 더 좋은 방법을 보고 공부하기로 했다.

기본적인 풀이는 완전 탐색(+ 백트래킹)으로 가능하다.

 

풀이의 핵심은 모든 카메라에서의 모든 방향의 경우의 수를 계산해서 최소 사각 지대의 개수를 구하는 것이다.

현재 경우의 수에서의 최소 사각 지대를 계속해서 갱신해 나간다.

 

반복을 간결하고, 가독성 있게 돌기 위해서 문제의 조건을 잘 구조화한 자료구조로 표현하는 것이 중요함을 깨달았다.

타입	방향 (0, 1, 2, 3 -> 동, 남, 서, 북)
1	[0], [1], [2], [3]
2	[0, 2], [1, 3]
3	[0, 1], [1, 2], [2, 3], [3, 0]
4	[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]
5	[0, 1, 2, 3]

모든 CCTV의 뱡항은 위와 같이 구조화할 수 있다.

이걸 코드로 표현하면 이렇게 된다.

static int[][][] directions = {
	{}, // 0번 카메라
	{{0}, {1}, {2}, {3}}, // 1번
	{{0, 2}, {1, 3}}, // 2번
	{{3, 0}, {0, 1}, {1, 2}, {2, 3}}, // 3번
	{{2, 3, 0}, {3, 0, 1}, {0, 1, 2}, {1, 2, 3}}, // 4번
	{{0, 1, 2, 3}}, // 5번
};

잘 구조화해두면 반복문을 작성하기 편하고, 가독성도 좋아진다.

// 모든 카메라의 모든 방향을 감시
for (int[] dirs : directions[cameraType]) {
    for (int dir : dirs) {
        // 감시 로직
    }
}

 

💡 같은 방향으로 전진하는 코드는 이렇게 작성할 수 있다.

while (true) {
    x += dx[direction];
    y += dy[direction];
}

 

코드

재귀를 사용한 풀이

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, m;
    static int[][] map;
    static List<int[]> cameras;
    static int[] dx = {0, 1, 0, -1}; // 동, 남, 서, 북
    static int[] dy = {1, 0, -1, 0};
    static int[][][] directions = {
            {}, // 0번 카메라
            {{0}, {1}, {2}, {3}}, // 1번
            {{0, 2}, {1, 3}}, // 2번
            {{3, 0}, {0, 1}, {1, 2}, {2, 3}}, // 3번
            {{2, 3, 0}, {3, 0, 1}, {0, 1, 2}, {1, 2, 3}}, // 4번
            {{0, 1, 2, 3}}, // 5번
    };
    static int minBlindSpot = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        // 5개의 CCTV
        // 1번은 한 쪽 방향, 2번은 반대 방향
        // 3번은 직각 방향, 4번은 세 방향, 5번은 네 방향
        // 벽이 없는 한 격자 끝까지 감시 가능, CCTV는 통과 가능
        // 카메라를 적절히 배치해 사각 지대를 최소화한다.
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        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());
            }
        }

        // 모든 카메라의 모든 방향에서의 최소 사작 지대를 구해야 한다.
        // 백트래킹으로 모든 카메라의 모든 방향에서의 사각 지대를 계산하고,
        // 모든 카메라의 사각 지대를 계산했으면, 종료 후 사각 지대 수를 갱신한다.
        // 계속 최솟값을 갱신하며 최소 사각 지대수를 구한다.
        cameras = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (1 <= map[i][j] && map[i][j] <= 5) {
                    cameras.add(new int[]{i, j});
                }
            }
        }

        findAllPath(0, map);
        System.out.println(minBlindSpot);
    }

    static void findAllPath(int depth, int[][] map) {
        // 모든 카메라의 위치를 조정했으면 최소 사각 지대를 갱신한다.
        if (depth == cameras.size()) {
            int currentBlind = countBlindSpots(map);
            minBlindSpot = Math.min(minBlindSpot, currentBlind);
            return;
        }

        int x = cameras.get(depth)[0];
        int y = cameras.get(depth)[1];
        int cameraType = map[x][y];

        // 모든 카메라에서의 모든 방향을 시도해본다.
        for (int[] dirs : directions[cameraType]) {
            // 현재 카메라의 모든 방향에 대해 맵 복사본을 생성
            int[][] currentMap = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    currentMap[i][j] = map[i][j];
                }
            }
            // 현재 카메라의 모든 방향을 감시한다.
            for (int dir : dirs) {
                watch(currentMap, x, y, dir);
            }
            findAllPath(depth + 1, currentMap);
        }
    }

    // 현재 맵, 현재 위치에서 dir 방향으로 감시 영역을 표시한다.
    static void watch(int[][] currentMap, int x, int y, int dir) {
        // 전진할 수 있는 만큼 같은 방향으로 계속 전진
        while (true) {
            x += dx[dir];
            y += dy[dir];

            if (!inRange(x, y) || currentMap[x][y] == 6) break;
            if (currentMap[x][y] == 0) currentMap[x][y] = 7; // 감시된 영역으로 표시
        }
    }

    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 boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
}

 

재귀를 사용하지 않은 풀이

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

public class Main {
    static int n, m;
    static int[][] map;
    static List<int[]> cctvs = new ArrayList<>();
    static int minBlindSpot = Integer.MAX_VALUE;

    static int[] dx = {0, 1, 0, -1}; // 동, 남, 서, 북
    static int[] dy = {1, 0, -1, 0};

    static int[][][] directions = {
            {},
            {{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];
        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 (1 <= map[i][j] && map[i][j] <= 5) {
                    cctvs.add(new int[]{i, j});
                }
            }
        }

        int[] maxRotations = new int[cctvs.size()];
        for (int i = 0; i < cctvs.size(); i++) {
            int type = map[cctvs.get(i)[0]][cctvs.get(i)[1]];
            maxRotations[i] = directions[type].length;
        }

        int total = 1;
        for (int r : maxRotations) total *= r;

        // 모든 방향 조합을 순차적으로 반복
        for (int comb = 0; comb < total; comb++) {
            int[][] tempMap = copyMap(map);

            int temp = comb;
            for (int i = 0; i < cctvs.size(); i++) {
                int[] cctv = cctvs.get(i);
                int type = map[cctv[0]][cctv[1]];
                int rotation = temp % maxRotations[i];
                temp /= maxRotations[i];

                for (int dir : directions[type][rotation]) {
                    watch(tempMap, cctv[0], cctv[1], dir);
                }
            }

            int blind = countBlindSpots(tempMap);
            minBlindSpot = Math.min(minBlindSpot, blind);
        }

        System.out.println(minBlindSpot);
    }

    static void watch(int[][] board, int x, int y, int dir) {
        while (true) {
            x += dx[dir];
            y += dy[dir];
            if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] == 6) break;
            if (board[x][y] == 0) board[x][y] = 7;
        }
    }

    static int countBlindSpots(int[][] board) {
        int count = 0;
        for (int[] row : board) {
            for (int cell : row) {
                if (cell == 0) count++;
            }
        }
        return count;
    }

    static int[][] copyMap(int[][] original) {
        int[][] copy = new int[n][m];
        for (int i = 0; i < n; i++) {
            copy[i] = Arrays.copyOf(original[i], m);
        }
        return copy;
    }
}