백준 15683번 : 감시 풀이(Java) - DFS

www.acmicpc.net/problem/15683

15683번: 감시

 

Solution

잘 안풀어본 유형이라 어려웠다. 아직 DFS 가 BFS에 비해 익숙하지 않은 것 같다. 교수님의 풀이 코드를 보고 실행 부분을 고쳤더니 해결이 되었다!

 

이 문제는 데이터의 범위가 굉장히 작기 때문에, 모든 cctv의 회전을 고려해도 된다. (브루트포스)

하지만 모든 cctv의 회전을 고려하는 상황을 만들기에 적합한 알고리즘이 DFS 였다.

 

사각지대에서 벗어난 빈 지역, 즉 CCTV로 관찰 가능한 0번의 경우를 9번으로 만들어주고, 모든 CCTV 의 경우를 다 보고난 뒤 남은 0의 갯수가 사각지대의 갯수이다.

 

나의 경우, 타입 5번, 상하좌우를 모두 보는 CCTV는 회전을 해봐야 결과가 같으므로, 입력을 받을 때 5번의 상하좌우를 9로 만들고 시작했다. 이제 카메라의 움직임을 주시해야 한다. 나는 switch 문을 쓰기 보다 3차원 배열로 한 방에 했다.

 

각 차원을 자세히 보면

 

• 타입의 갯수가 4가지( 5번 제외, 1~4 이므로 4 + 1 크기의 1차원)
• 각 타입별로, 회전하지 않았을 때, 회전 1번, 2번, 3번 즉 볼 수 있는 방향의 경우의 수가 4가지(4 크기의 2차원)
• 1번 타입의 경우는 한 번에 한 방향, 2번 3번의 경우는 두 방향, 4번의 경우는 3방향 (각각 1, 2, 3 크기의 3차원)

이다.

상하좌우를 0,1,2,3 등으로 표현하면 반드시 헷갈릴 것 같아서 상수로 보기 좋게 표현해줬다. 사실 숫자에 크게 의미는 없다. 비교를 위한 것.

private static final int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3, WALL = 6, CAN_SEE = 9;
private static int[][][] d = {{}, // 타입 0번은 없다
{{RIGHT},{DOWN},{LEFT},{UP}},  // 타입 1번
{{LEFT, RIGHT}, {UP, DOWN}, {LEFT, RIGHT}, {UP,DOWN}}, //2번
{{UP,RIGHT}, {RIGHT, DOWN}, {DOWN, LEFT}, {LEFT, UP}}, //3번 
{{UP,LEFT,RIGHT},{ UP,RIGHT,DOWN},{RIGHT,DOWN,LEFT},{DOWN,LEFT,UP}}}; // 4번

 

다음은 이렇게 만든 d를 기반으로, cctv의 위치를 기반으로 UP,DOWN,LEFT, RIGHT 각각에 따라 지역을 감시하는 메서드를 만들어준다.

private static void show(int[][] map, int cameraX, int cameraY, int showDir) {
        if(showDir == UP) {
            for(int x = cameraX; x >= 0; x--) {
                if(map[x][cameraY] == WALL) break; // 벽을 마주치면 더 볼 수 없다.
                if(map[x][cameraY] == 0 || map[x][cameraY] == CAN_SEE) {
                    // 관찰 가능한 0번이거나, 이미 관찰한 9번이라면
                    map[x][cameraY] = CAN_SEE;
                }
            }
        } else if(showDir == DOWN) {
            for(int x = cameraX; x < N; x++) {
                if(map[x][cameraY] == WALL) break;
                if(map[x][cameraY] == 0 || map[x][cameraY] == CAN_SEE) {
                    map[x][cameraY] = CAN_SEE;
                }
            }
        }else if(showDir == LEFT) {
            for(int y = cameraY; y >= 0; y--) {
                if(map[cameraX][y] == WALL) break;
                if(map[cameraX][y] == 0 ||map[cameraX][y] == CAN_SEE) {
                    map[cameraX][y] = CAN_SEE;
                }
            }
        }else if(showDir == RIGHT) {
            for(int y = cameraY; y < M; y++) {
                if(map[cameraX][y] == WALL) break;
                if(map[cameraX][y] == 0 ||map[cameraX][y] == CAN_SEE) {
                    map[cameraX][y] = CAN_SEE;
                }
            }
        }
 }

마지막으로, 전체 경우의 수를 돌아줄 DFS 메서드를 만들어준다.

private static void dfs(int idx, int[][] map) {
        if(idx == cameras.size()) { // 기저조건 : 모든 카메라를 다 돌았다면 종료
            answer = Math.min(answer, getEdgeCount(map));
            // map 에서 0의 갯수를 센 것과, answer 중 작은 것을 저장한다.
            return;
        }
        Camera camera = cameras.get(idx); // 해당 인덱스의 카메라를 가져오고
        int x = camera.x;
        int y = camera.y;
        int[][] newMap = new int[N][M];
        for(int i = 0 ; i < 4 ; i++) { // 회전횟수 4회를 돌면서
            int[] next = d[camera.type][i]; // 카메라의 타입(1차원) -> 회전 횟수에 따른 움직임들(2차원)
            newMap = copyMap(map); // 이전의 map 을 복사해준다. (서로에게 영향을 끼치지 않기 위해)
            for(int j = 0; j < next.length; j++) {
            	// {LEFT, RIGHT, DOWN}  일 경우, LEFT->RIGHT->DOWN 을 감시해준다.
                show(newMap, x, y, next[j]);
            }
            // 이러면, i번 회전한 카메라로 여러 방향을 감시한 결과가 newMap 에 저장되고
            dfs(idx + 1, newMap);
           	// 재귀로 넘겨준다.
        }
    }

이제 합치면 끝이다.

Source Code

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

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N,M,answer;
    private static int[][] map;
    private static ArrayList<Camera> cameras;
    // 1번 : RIGHT -> DOWN -> LEFT -> UP
    // 2번 : LEFT, RIGHT -> UP, DOWN -> LEFT, RIGHT -> UP, DOWN
    // 3번 : UP, RIGHT -> RIGHT, DOWN -> DOWN, LEFT -> LEFT, UP
    // 4번 : UP, LEFT, RIGHT -> UP, RIGHT, DOWN -> RIGHT, DOWN, LEFT -> DOWN, LEFT, UP
    private static final int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3, WALL = 6, CAN_SEE = 9;
    private static int[][][] d = {{}, {{RIGHT},{DOWN},{LEFT},{UP}}, {{LEFT, RIGHT}, {UP, DOWN}, {LEFT, RIGHT}, {UP,DOWN}}, {{UP,RIGHT}, {RIGHT, DOWN}, {DOWN, LEFT}, {LEFT, UP}}, {{UP,LEFT,RIGHT},{ UP,RIGHT,DOWN},{RIGHT,DOWN,LEFT},{DOWN,LEFT,UP}}};

    private static class Camera {
        int x;
        int y;
        int type;

        public Camera(int x, int y, int type) {
            this.x = x;
            this.y = y;
            this.type = type;
        }

        @Override
        public String toString() {
            return "Camera{" +
                    "x=" + x +
                    ", y=" + y +
                    ", type=" + type +
                    '}';
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    private static void input() throws IOException {
        StringTokenizer nm = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nm.nextToken());
        M = Integer.parseInt(nm.nextToken());
        map = new int[N][M];
        answer = Integer.MAX_VALUE;
        cameras = new ArrayList<>();
        for(int i = 0 ; i < N; i++) {
            StringTokenizer line = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0 ; j < M; j++) {
                map[i][j] = Integer.parseInt(line.nextToken());
                if(map[i][j] > 0 && map[i][j] < 6) {
                    cameras.add(new Camera(i,j, map[i][j]));
                }
            }
        }
        ArrayList<Camera> newCameras = new ArrayList<>();
        for(Camera c : cameras) {
            if(c.type == 5) {
                show(map, c.x, c.y, UP);
                show(map, c.x, c.y, DOWN);
                show(map, c.x, c.y, RIGHT);
                show(map, c.x, c.y, LEFT);
            } else {
                newCameras.add(c);
            }
        }
        cameras = newCameras;
    }

    private static int getEdgeCount(int[][] map) {
        int sum = 0;
        for(int i = 0 ; i < N; i++) {
            for(int j = 0 ; j < M; j++) {
                if(map[i][j] == 0) sum++;
            }
        }
        return sum;
    }

    private static void printMap(int[][] map) {
        for(int i = 0 ; i < N; i++) {
            for(int j = 0 ; j < M; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("====================");
    }

    private static int[][] copyMap(int[][] map) {
        int[][] result = new int[N][M];
        for(int i = 0 ; i < N; i++) {
            result[i] = map[i].clone();
        }
        return result;
    }


    private static void show(int[][] map, int cameraX, int cameraY, int showDir) {
        if(showDir == UP) {
            for(int x = cameraX; x >= 0; x--) {
                if(map[x][cameraY] == WALL) break;
                if(map[x][cameraY] == 0 || map[x][cameraY] == CAN_SEE) {
                    map[x][cameraY] = CAN_SEE;
                }
            }
        } else if(showDir == DOWN) {
            for(int x = cameraX; x < N; x++) {
                if(map[x][cameraY] == WALL) break;
                if(map[x][cameraY] == 0 || map[x][cameraY] == CAN_SEE) {
                    map[x][cameraY] = CAN_SEE;
                }
            }
        }else if(showDir == LEFT) {
            for(int y = cameraY; y >= 0; y--) {
                if(map[cameraX][y] == WALL) break;
                if(map[cameraX][y] == 0 ||map[cameraX][y] == CAN_SEE) {
                    map[cameraX][y] = CAN_SEE;
                }
            }
        }else if(showDir == RIGHT) {
            for(int y = cameraY; y < M; y++) {
                if(map[cameraX][y] == WALL) break;
                if(map[cameraX][y] == 0 ||map[cameraX][y] == CAN_SEE) {
                    map[cameraX][y] = CAN_SEE;
                }
            }
        }
    }

    private static void dfs(int idx, int[][] map) {
        if(idx == cameras.size()) {
            answer = Math.min(answer, getEdgeCount(map));
            return;
        }
        Camera camera = cameras.get(idx);
        int x = camera.x;
        int y = camera.y;
        int[][] newMap = new int[N][M];
        for(int i = 0 ; i < 4 ; i++) {
            int[] next = d[camera.type][i];
            newMap = copyMap(map);
            for(int j = 0; j < next.length; j++) {
                show(newMap, x, y, next[j]);
            }
            dfs(idx + 1, newMap);
        }
    }

    private static void solve() throws IOException {
        dfs(0, map);
        System.out.println(answer);
    }
}