[백준 Gold 5] 15683 감시 - Java

문제링크 : https://www.acmicpc.net/problem/15683

15683번: 감시

 

접근 과정 : 

• CCTV의 방향을 다 돌려보면서 완전탐색했다.
• 관건은. CCTV방향을 얼마나 효율적으로 돌리느냐 라고 생각했다.
• 방향을 상하좌우로 나눠서 어떤 하나의 방향이 주어질 때, 그 방향으로 모두 감시하는 함수를 설정하고
• 카메라의 종류에 따라 방향들을 주면서 확인했다.
• 카메라가 보고 있는 곳은 int[][] 에서 -1 시켜가면서 체크했다.
• dfs로 카메라를 하나하나, 카메라의 종류에 따라서 그 방향을 하나하나 체크해가면서 최소 사각지대를 확인했다. 

 

소스 코드 및 결과 :

package BOJ;

/* 
    감시
*/

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

public class BOJ15683 {

    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];
        cctvList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int t = Integer.parseInt(st.nextToken());

                if (t > 0 && t < 6) {
                    cctvList.add(new Cctv(i, j, t));
                    office[i][j] = -1;
                } else if (t == 6) {
                    office[i][j] = 6;
                }
            }

        }

        blind = N * M;

        dfs(0);

        System.out.println(blind);

    }

    static int N, M, blind;
    static int[][] office;
    static List<Cctv> cctvList;

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

    private static class Cctv {
        int r;
        int c;
        int type;

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

    }

    static void dfs(int index) {

        if (index == cctvList.size()) {
            // 사각지대 체크.
            int sum = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {

                    if (office[i][j] == 0) {
                        sum++;
                    }
                }
            }

            blind = Math.min(blind, sum);

            return;
        }

        // cctv 방향 변경

        rotate(index);

    }

    static void watch(int r, int c, int d) {

        int nr = r;
        int nc = c;
        while (true) {
            nr += dir[d][0];
            nc += dir[d][1];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M || office[nr][nc] == 6) {
                break;
            }
            office[nr][nc]--;

        }

        return;

    }

    static void unDoWatch(int r, int c, int d) {
        int nr = r;
        int nc = c;
        while (true) {
            nr += dir[d][0];
            nc += dir[d][1];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M || office[nr][nc] == 6) {
                break;
            }
            office[nr][nc]++;

        }

        return;

    }

    static void rotate(int index) {

        if (index == cctvList.size()) {

            return;
        }

        int r = cctvList.get(index).r;
        int c = cctvList.get(index).c;
        int t = cctvList.get(index).type;

        switch (t) {
            case 1:

                for (int i = 0; i < 4; i++) {

                    watch(r, c, i);
                    dfs(index + 1);
                    unDoWatch(r, c, i);

                }

                break;
            case 2:

                for (int i = 0; i < 2; i++) {

                    watch(r, c, i);
                    watch(r, c, (i + 2) % 4);

                    dfs(index + 1);

                    unDoWatch(r, c, i);
                    unDoWatch(r, c, (i + 2) % 4);
                }
                break;

            case 3:

                watch(r, c, 0);
                watch(r, c, 1);

                for (int i = 0; i < 4; i++) {
                    dfs(index + 1);
                    unDoWatch(r, c, i);
                    watch(r, c, (i + 2) % 4);
                }

                unDoWatch(r, c, 0);
                unDoWatch(r, c, 1);

                break;
            case 4:

                watch(r, c, 1);
                watch(r, c, 2);
                watch(r, c, 3);

                for (int i = 0; i < 4; i++) {

                    dfs(index + 1);

                    watch(r, c, i);
                    unDoWatch(r, c, (i + 1) % 4);
                }

                unDoWatch(r, c, 1);
                unDoWatch(r, c, 2);
                unDoWatch(r, c, 3);

                break;

            default: // 5
                watch(r, c, 0);
                watch(r, c, 1);
                watch(r, c, 2);
                watch(r, c, 3);

                dfs(index + 1);

                unDoWatch(r, c, 0);
                unDoWatch(r, c, 1);
                unDoWatch(r, c, 2);
                unDoWatch(r, c, 3);
                break;
        }

        return;

    }

}

 

P.S 

어떻게 해야 더 효율적일지 모르겠다.. 그냥 극강의 노가다, 시뮬레이션인 것 같다.

watch / unDoWatch 체크만 방향을 생각해서 최대한 겹치지 않게 돌렸다..

중간에 방향을 헷갈려서 실수가 많이 생겼다.

6(벽)을 사각지대에 포함시키는 실수도 하고...