[백준 15683번] 감시

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

package implement;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Impl15683 {
    static int N;
    static int M;

    static int[][] map;

    static int min;

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

    static List<int[]> cctvs;

    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];
        cctvs = new ArrayList<>();
        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] != 0 && map[i][j] != 6) {
                    cctvs.add(new int[]{i, j});
                }
            }
        }

        min = N * M;
        cctvSolve(0);
        System.out.println(min);

    }

    // 1은 북 2는 동 3은 남 4는 서 dir
    public static void cctvSolve(int depth) {
        if (depth == cctvs.size()) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 0) {
                        sum++;
                    }
                }
            }
            min = Math.min(min, sum);
            return;
        }

        int[] cctvPlace = cctvs.get(depth);
        int sx = cctvPlace[0];
        int sy = cctvPlace[1];

        for (int dir = 1; dir < 5; dir++) {
            search(sx, sy, dir, true);
            cctvSolve(depth + 1);
            search(sx, sy, dir, false);
        }
    }


    static void search(int x, int y, int dir, boolean flag) {
        if (map[x][y] == 1) fill(dir, x, y, flag);
        else if (map[x][y] == 2) {
            int fDir = dir + 2 >= 5 ? dir - 2 : dir + 2;
            fill(dir, x, y, flag);
            fill(fDir, x, y, flag);
        } else if (map[x][y] == 3) {
            int fDir = dir + 1 >= 5 ? dir - 3 : dir + 1;
            fill(dir, x, y, flag);
            fill(fDir, x, y, flag);
        } else if (map[x][y] == 4) {
            int fDir = dir + 2 >= 5 ? dir - 2 : dir + 2;
            for (int i = 1; i < 5; i++) {
                if (i == fDir) {
                    continue;
                }
                fill(i, x, y, flag);

            }
        } else {
            for (int i = 1; i < 5; i++) {
                fill(i, x, y, flag);
            }
        }


    }

    static void fill(int dir, int x, int y, boolean flag) {

        if (flag) {
            int nX = x + dx[dir - 1];
            int nY = y + dy[dir - 1];

            if (nX >= 0 && nX < N && nY >= 0 && nY < M) {
                if (map[nX][nY] != 6) {
                    if (map[nX][nY] == 0) {
                        map[nX][nY] = 7;
                    } else if (map[nX][nY] >= 7) {
                        map[nX][nY] += 1;
                    }
                    fill(dir, nX, nY, true);
                }
            }
        } else {
            int nX = x + dx[dir - 1];
            int nY = y + dy[dir - 1];

            if (nX >= 0 && nX < N && nY >= 0 && nY < M) {
                if (map[nX][nY] != 6) {
                    if (map[nX][nY] > 7) {
                        map[nX][nY] -= 1;
                    } else if (map[nX][nY] == 7) {
                        map[nX][nY] = 0;
                    }
                    fill(dir, nX, nY, false);
                }
            }
        }
    }
}

 

와, 이건 1시간 반이나 걸린 문제였다.
BFS로 방향 탐색을 하는 문제인데, CCTV의 방향이 단순히 1뿐만 아니라 2나 3처럼 다양한 경우가 있어서, 어떻게 하면 효율적으로 방향을 탐색할 수 있을까 고민을 정말 많이 했다.

 

결국 핵심은 조건부 표현식(삼항 연산자)을 활용해 방향 값을 효율적으로 추출하는 방식으로 해결했다.
또한, 함수가 끝났을 때 상태를 되돌려야 하므로, 값을 추가할 때 7 이상으로 설정하고, 감소만 시켜주는 방식으로 처리했다.
그리고 값이 7일 때는 0으로 설정하면된다. 이렇게 7 이상으로 값을 늘린 이유는 CCTV끼리 감시 범위가 겹칠 수 있기 때문이다.

그리고 시간 초과를 막기 위해 cctvSolve 함수에서는 이중 for문을 제거해서 탐색 효율도 개선했다.

 

다른 사람들 풀이도 몇 개 봤는데, 내 코드가 훨씬 깔끔하고 잘 짜인 것 같다.