[백준] 15683. 감시 (Java)

DFS 백트래킹 문제에 cctv를 설치하는 부분만 신경써주면 쉬운 문제

 

 

15683번: 감시

 

풀이

CCTV의 5가지 종류에 대해 조합으로 방향 정보를 구성하고 DFS를 짜주면 끝나는 간단한 문제이다.

 

방향 정보를 어떻게 나타낼지 고민을 많이 했다..

우선 처음에 사무실 정보를 입력받을 때 카메라 번호 및 위치, 그리고 해당 카메라의 방향 정보 개수 (d)를 ArrayList에 넣는다. 방향 정보 개수는 아래 그림과 같다.

 

 

 

 

 

 

방문체크는 visited 2차원 배열을 만들어 해당 depth에 어떤 방향을 선택했는지 나타냈다. 예를들어 카메라가 3개 있다고 하면 아래처럼 방문체크가 되겠다.

 

 

 

카메라의 설치는 install이라는 method를 만들고 status 변수값에 따라 설치와 해체를 동시에 할 수 있게 했다.

 

이때 카메라가 겹칠 수 있으므로 해당 위치의 값을 갱신하면 백트래킹하면서 겹치는 카메라까지 없애버리기 때문에 사각지대 카운팅이 제대로 안된다. 따라서 +-로 해주는 것이 포인트이다.

나는 final int CAM 변수를 만들어서 처리했다.

 

카메라의 설치는 카메라 종류에 따라 case를 나누어서 했다. changeStatus method에서 범위를 벗어나거나 벽 (6)을 만나기 전까지 해당 위치에 status 값을 더해주었다.

 

카메라 해체의 경우 status 값에 음수를 넣었다.

 

 

Logic

1. 카메라 위치 및 방향 정보 개수, 카메라 번호를 ArrayList에 저장한다.
2. DFS를 수행한다. 이때 카메라를 설치한다.
3. depth가 카메라 개수가 되면 사각지대 크기를 세서 작은 값으로 갱신한다.
4. 3에서 return되면 설치했던 카메라를 해체한다.
5. 2~4 반복 후 최종 답을 출력한다.

 

 

코드

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

public class Main {
    static final int CAM = 10;
    static int N, M, ans;
    static ArrayList<CCTV> cctv = new ArrayList<>();
    static int[][] map;
    static boolean[][] visited = new boolean[10][5];
    static int[] pos_x = { 0, -1, 0, 1 };
    static int[] pos_y = { 1, 0, -1, 0 };

    public static void main(String[] args) throws IOException {
        input();
        solve(0);
        System.out.println(ans);
    }

    public static void input() 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 + 2][M + 2];
        ans = N * M;

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

            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (1 <= map[i][j] && map[i][j] <= 5)
                    cctv.add(new CCTV(i, j, map[i][j], getDirection(map[i][j])));
            }
        }
        br.close();
    }

    public static void solve(int depth) {
        if (depth == cctv.size()) {
            ans = Math.min(ans, getDeadGround());
            return;
        }

        for (int i = 0; i < cctv.get(depth).n; i++) {
            if (visited[depth][i]) continue;
            visited[depth][i] = true;
            install(cctv.get(depth).x, cctv.get(depth).y, cctv.get(depth).cam, i, CAM);
            solve(depth + 1);
            visited[depth][i] = false;
            install(cctv.get(depth).x, cctv.get(depth).y, cctv.get(depth).cam, i, -CAM);
        }
    }

    public static int getDeadGround() {
        int sum = 0;

        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (map[i][j] == 0) sum++;

        return sum;
    }

    public static void print() {
        System.out.println("result: ");
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                System.out.printf("%3d", map[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }

    // cctv 설치 및 해체
    public static void install(int x, int y, int cam, int d, int status) {
        changeStatus(x, y, d, status);
        if (cam == 3 || cam == 4 || cam == 5)
            changeStatus(x, y, d + 1, status);
        if (cam == 2 || cam == 4 || cam == 5)
            changeStatus(x, y, d + 2, status);
        if (cam == 5)
            changeStatus(x, y, d + 3, status);
    }

    public static void changeStatus(int x, int y, int d, int status) {
        d %= 4;
        // p: prev, n: next
        int px = x, py = y, nx, ny;
        while(true) {
            nx = px + pos_x[d];
            ny = py + pos_y[d];

            if (!isIn(nx, ny)) break;

            map[nx][ny] += status;
            px = nx;
            py = ny;
        }
    }

    public static boolean isIn(int x, int y) {
        if (x < 1 || x > N || y < 1 || y > M || map[x][y] == 6)
            return false;

        return true;
    }

    public static int getDirection(int d) {
        int direction = 0;

        switch(d) {
        case 1:
        case 3:
        case 4:
            direction = 4;
            break;
        case 2:
            direction = 2;
            break;
        case 5:
            direction = 1;
            break;
        }

        return direction;
    }

    static class CCTV {
        int x;
        int y;
        int cam;
        int n;

        public CCTV(int x, int y, int cam, int n) {
            this.x = x;
            this.y = y;
            this.cam = cam;
            this.n = n;
        }


    }
}

실행 결과