[BOJ] 15683:감시

0. 문제

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

15683번: 감시

 

1. 문제분석

- 8개 이하의 cctv들이 만들어낼 수 있는 사각지대의 넓이를 구하기 위해서는, 각 cctv들이 감시할 수 있는 경우의 수를 모두 고려해 보아야 한다. 즉, 각 cctv들이 움직일 수 있는 경우의 수 대로 사각지대 넓이를 각각 구해보고 그 최솟값을 구해야 하므로, cctv들이 감시할 수 있는 영역을 순차적으로 대입시켜보고, 다시 원래 상태로 복구한 뒤에 새로운 경우의 수를 대입시키는 방식으로 코드를 작성해야 한다. 따라서 n-queen 문제를 푸는 것과 마찬가지로  백트래킹(backtracking)을 사용해 문제를 풀어야 한다. 

 

2. 주의할 점

- 백트래킹 시, 감시가 이루어진 위치가 여러 개의 cctv에 의해서 여러 번의 감시가 이루어질 수 있음에 유의해야 한다. 즉, 하나의 경우의 수일 때 결과를 확인한 뒤, 다음 경우의 수를 대입시키기 위해 그리드(2차원 배열)를 원상복구 시킬 때에 있어서, 해당 위치가 반드시 지금의 경우의 수를 대입한 결과에 의해서만 감시되지는 않았음을 확인해야 한다.

 

3. 소스코드(Java)

// boj 15683 감시
// backtracking

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.Vector;

public class boj_15683 {
    static int n,m;
    static int[][] grid;
    static int ans = 987654321;
    static int [][] cams;
    static final int[][][][] cctv = {
            {},
            {
                {{-1,0}},
                {{0,1}},
                {{1,0}},
                {{0,-1}}
            },
            {
                {{-1,0},{1,0}},
                {{0,1},{0,-1}}
            },
            {
                {{-1,0},{0,1}},
                {{0,1},{1,0}},
                {{1,0},{0,-1}},
                {{0,-1},{-1,0}}
            },
            {
                {{0,-1},{-1,0},{0,1}},
                {{-1,0},{0,1},{1,0}},
                {{0,1},{1,0},{0,-1}},
                {{1,0},{0,-1},{-1,0}}
            },
            {
                {{-1,0},{0,1},{1,0},{0,-1}}
            }
    };
    static final int BLANK = 0;
    static final int WALL = 6;
    static final int SHADE = 7;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        grid = new int[n][m];
        Vector<int[]> tmpCams = new Vector<>();
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; ++j) {
                grid[i][j] = stoi(st.nextToken());
                if (1 <= grid[i][j] && grid[i][j] <= 5) tmpCams.add(new int[]{i, j});
            }
        }
        cams = tmpCams.toArray(new int[tmpCams.size()][2]);
        go(0);
        System.out.print(ans);
    }
    public static int stoi(String s) {return Integer.parseInt(s);}
    public static void go(int camIdx) {
        if (camIdx == cams.length) {
            int blankCnt = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j)
                    if (grid[i][j] == BLANK) blankCnt++;
            }
            if (blankCnt < ans) ans = blankCnt;
            return;
        }
        int nowCctv = grid[cams[camIdx][0]][cams[camIdx][1]];
        for (int[][] dirs: cctv[nowCctv]) {
            draw(cams[camIdx][0], cams[camIdx][1], SHADE, dirs);
            go(camIdx + 1);
            draw(cams[camIdx][0], cams[camIdx][1], -SHADE, dirs);
        }
    }
    public static void draw(int r, int c, int toDraw, int[][] dirs) {
        for (int[] dir: dirs) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            while (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                if (grid[nr][nc] == WALL) break;
                if (grid[nr][nc] == BLANK || grid[nr][nc] >= SHADE)
                    // 단순히 감시의 유무만 확인하지 말고, 몇 번의 감시가 누적되는지 확인!!
                    grid[nr][nc] += toDraw;
                nr += dir[0];
                nc += dir[1];
            }
        }
    }
}

 

4. 여담

- 파이팅!