[JAVA] 백준 15683 감시

 

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

 

백트래킹 문제였습니다. 

1. CCTV 클래스를 만들기. CCTV는 위치정보와 CCTV타입을 가지고 있음.
2. cctvList를 만들어 CCTV들을 저장
3. 경우의 수를 모두 구해 사각지대 최솟값 도출

문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다.

코드가 상당히 길게 나왔는데 문제의 핵심은 dfs메서드의 이 부분입니다.

		CCTV now = cctvList.get(depth);
        // cctv의 타입에 따라
        switch (now.type) {
            case 1:
                // dir은 방향, 1번 유형은 4개의 경우의 수
                for (int dir = 0; dir < 4; dir++) {
                    // map의 정보를 copy에 복사해놓고
                    copy(map, copy);
                    move(now, dir);
                    dfs(depth + 1);
                    // 원상복구 시킴
                    copy(copy, map);
                }
                break;
            case 2:
                // 2번 유형은 2개의 경우의 수
                for (int dir = 0; dir < 2; dir++) {
                    copy(map, copy);
                    move(now, dir);
                    move(now, (dir + 2) % 4);
                    dfs(depth + 1);
                    copy(copy, map);
                }
                break;
            case 3:
                for (int dir = 0; dir < 4; dir++) {
                    copy(map, copy);
                    move(now, dir);
                    move(now, (dir + 1) % 4);
                    dfs(depth + 1);
                    copy(copy, map);
                }
                break;
            case 4:
                for (int dir = 0; dir < 4; dir++) {
                    copy(map, copy);
                    move(now, dir);
                    move(now, (dir + 1) % 4);
                    move(now, (dir + 2) % 4);
                    dfs(depth + 1);
                    copy(copy, map);
                }
                break;
            case 5:
                // 5번 유형은 4방향 다 감시하므로 하나의 경우의 수 밖에 없음
                copy(map, copy);
                // 1방향씩 네번 반복하니까 4방향 다 본다는 의미, 일일이 move(now, dir+1), move(now, dir+2)... 해도 상관 X
                for (int dir = 0; dir < 4; dir++) {
                    move(now, dir);
                }
                dfs(depth + 1);
                copy(copy, map);
                break;
        }

 

주석을 달아놨지만 추가적으로 설명을 해보겠습니다.

 

switch문은 cctv의 유형에 따라 작동합니다. 

 

copy는 깊은복사 메서드입니다. 각 경우의 수를 살펴보려면 원본 map과 변화한 map을 가지고 있어야 합니다. copy메서드는 이를 위한 백업이라고 생각하면 편합니다.

 

1. copy로 map 배열을 copy 배열에 백업

2. move로 맵에 변화를 주고 dfs(depth+1)에서 넘김

3. 백업해놓은 copy를 map으로 원상복구

 

전체코드

 

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class CCTV {
    int x;
    int y;
    int type;

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

public class Main {
    static int N, M;
    static int result = Integer.MAX_VALUE;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static int[][] map;
    static ArrayList<CCTV> cctvList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];

        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());
                // 만약 0이 아니고 6(벽)이 아니면 cctv 이므로 넣어줌
                if (map[i][j] != 0 && map[i][j] != 6) {
                    cctvList.add(new CCTV(i, j, map[i][j]));
                }
            }
        }

        dfs(0);

        System.out.println(result);

    }

    static void dfs(int depth) {
        // cctv의 갯수
        int size = cctvList.size();

        if (depth == size) {
            // check 메서드로 경우의 수 별 사각지대의 갯수를 구하고 최솟값을 구함
            result = Math.min(result, check());
            return;
        }

        // 백업용 copy배열
        int[][] copy = new int[N][M];

        CCTV now = cctvList.get(depth);
        // cctv의 타입에 따라
        switch (now.type) {
            case 1:
                // dir은 방향, 1번 유형은 4개의 경우의 수
                for (int dir = 0; dir < 4; dir++) {
                    // map의 정보를 copy에 복사해놓고
                    copy(map, copy);
                    move(now, dir);
                    dfs(depth + 1);
                    // 원상복구 시킴
                    copy(copy, map);
                }
                break;
            case 2:
                // 2번 유형은 2개의 경우의 수
                for (int dir = 0; dir < 2; dir++) {
                    copy(map, copy);
                    move(now, dir);
                    move(now, (dir + 2) % 4);
                    dfs(depth + 1);
                    copy(copy, map);
                }
                break;
            case 3:
                for (int dir = 0; dir < 4; dir++) {
                    copy(map, copy);
                    move(now, dir);
                    move(now, (dir + 1) % 4);
                    dfs(depth + 1);
                    copy(copy, map);
                }
                break;
            case 4:
                for (int dir = 0; dir < 4; dir++) {
                    copy(map, copy);
                    move(now, dir);
                    move(now, (dir + 1) % 4);
                    move(now, (dir + 2) % 4);
                    dfs(depth + 1);
                    copy(copy, map);
                }
                break;
            case 5:
                // 5번 유형은 4방향 다 감시하므로 하나의 경우의 수 밖에 없음
                copy(map, copy);
                // 1방향씩 네번 반복하니까 4방향 다 본다는 의미, 일일이 move(now, dir+1), move(now, dir+2)... 해도 상관 X
                for (int dir = 0; dir < 4; dir++) {
                    move(now, dir);
                }
                dfs(depth + 1);
                copy(copy, map);
                break;
        }

    }

    // cctv가 바라보는 부분을 -1로 하는 move 메서드
    static void move(CCTV c, int dir) {
        int nr = c.x;
        int nc = c.y;
        while (true) {
            nr = nr + dr[dir];
            nc = nc + dc[dir];
            // map 범위를 벗어나거나 벽을 만낫을때 종료
            if (nr < 0 || nc < 0 || nr >= N || nc >= M || map[nr][nc] == 6) {
                break;
            }
            map[nr][nc] = -1;
        }
    }

    // 깊은복사
    static void copy(int[][] map, int[][] copy) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copy[i][j] = map[i][j];
            }
        }
    }

    // 0의 갯수 -> 사각지대의 갯수이므로 check 메서드를 통해 각 경우의 수 별 사각지대의 갯수를 구할 수 있음
    static int check() {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    cnt++;
                }
            }
        }
        return cnt;
    }


    // 확인용 print
    static void print() {
        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();
    }
}

 

많이 부족한 코드입니다. 수정할 점, 잘못된 점, 개선점 보이면 말씀해주세요!!

감사합니다.