[백준 JAVA] 15683. 감시

문제 링크

---

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

접근 방법

---

모든 CCTV의 방향을 백트래킹으로 탐색하면서, 각 조합에 대해 사각지대의 최소 크기를 갱신합니다.
CCTV의 감시 방향에 따라 감시 영역을 표시하고, 되돌리는 과정을 통해 모든 경우를 탐색합니다.

소스 코드

---

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

public class Main {

    static int n, m, noSagak = 0, cnt = 0, rst = 65;
    static int[] dy = {0, 1, 0, -1}, dx = {1, 0, -1, 0};
    static int[][] office;
    static List<int[]> cctv;
    static int[][][] type = {
        {},
        { { 0 }, { 1 }, { 2 }, { 3 } },
        { { 0, 2 }, { 1, 3 } },
        { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 0 } },
        { { 0, 1, 2 }, { 1, 2, 3 }, { 2, 3, 0 }, { 3, 0, 1 } },
        { { 0, 1, 2, 3 } }
    };

    static int gamsi(int startY, int startX, int i, int idx) {
        int tmp = 0, y = startY + dy[i], x = startX + dx[i];

        while (y >= 0 && y < n && x >= 0 && x < m) {
            if (office[y][x] == 6) {
                break;
            } else if (office[y][x] ==  0) {
                office[y][x] = idx;
                ++tmp;
            }
            y += dy[i];
            x += dx[i];
        }

        return tmp;
    }

    static void reverseGamsi(int startY, int startX, int i, int idx) {
        int y = startY + dy[i], x = startX + dx[i];

        while (y >= 0 && y < n && x >= 0 && x < m) {
            if (office[y][x] == 6) {
                break;
            } else if (office[y][x] == idx) {
                office[y][x] = 0;
            }
            y += dy[i];
            x += dx[i];
        }
    }

    static void recursive(int idx) {
        if (cctv.size() == idx) {
            int tmp = m * n - noSagak - cnt;

            rst = rst > tmp ? tmp : rst;
            return;
        }

        int[] coor = cctv.get(idx);

        for (int[] orders : type[office[coor[0]][coor[1]]]) {
            int tmp = 0;

            for (int order : orders) {
                tmp += gamsi(coor[0], coor[1], order, idx + 7);
            }

            cnt += tmp;
            recursive(idx + 1);
            cnt -= tmp;

            for (int order : orders) {
                reverseGamsi(coor[0], coor[1], order, idx + 7);
            }
        }
    }

    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());
        office = new int[n][m];
        cctv = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                int tmp = Integer.parseInt(st.nextToken());

                if (tmp == 6) {
                    ++noSagak;
                } else if (tmp != 0) {
                    cctv.add(new int[]{i, j});
                    ++noSagak;
                }
                office[i][j] = tmp;
            }
        }

        recursive(0);

        System.out.println(rst);
    }
}

코드 설명

---

각 CCTV의 좌표를 리스트에 저장한 후, 각 타입에 따른 가능한 방향 조합을 순회합니다.
감시 영역을 지정된 번호(idx + 7)로 덮고, 백트래킹을 통해 모든 경우를 되돌리며 최소 사각지대 크기를 갱신합니다.