[백준] 15683 : 감시 <JAVA>

백준 문제 링크

 

 

간단 문제 설명 

총 5가지 종류의 회전 가능한 CCTV 방향을 설정하여 CCTV 사각지대의 최솟값 구하기

CCTV 종류별 감시 방향, 90도씩 회전 가능

 

 

고민 내용

1. 그리디 알고리즘으로 문제를 해결하고 싶었지만, 풀 수 없었다.

• 각 단계의 최적의 방향이 최솟값을 만들 수 못할 수 있다

• 방향 별 감시할 수 있는 영역의 수가 동일할 때 방향을 설정하는 기준을 찾지 못했다.

 

 

👉🏻 완전탐색 알고리즘이 제한된 시간을 초과할 수 있을 것 같아 그리디 알고리즘을 사용했지만 실패했다. 해당 문제를 구글링한 결과 CCTV의 최대 개수가 8개로 작아 완전탐색으로 풀 수 있었다.

 

완전탐색 알고리즘

코딩 테스트에서 완전탐색 알고리즘은 시간제한 문제가 발생할 수 있기 때문에 피하려고 노력했다. 하지만 문제에서 CCTV의 개수를 8개로 제한하여 N 값이 작아 완전탐색 알고리즘을 사용해도 시간제한 안에 해결할 수 있었다.

 

N이 작다고 판단할 수 있는 기준을 찾아봤다. 코딩테스트 환경에서 보통 1초에 약 1억 번 (10⁸) 연산이 가능하다. 하지만, 자바는 C/C++ 보다 실행속도가 느린 경우가 많고 자료구조 사용, 조건문 검사 등 시간이 오래 걸릴 수 있어서 10⁶을 기준으로 잡고 문제를 풀면 좋을 것 같다:)

 

문제에서 CCTV의 최대 개수는 8개이고 CCTV 방향은 상하좌우 4개이다 👉🏻 총경우의 수 = 4^N

(4^8 = 65,536)  <  10⁶ 이므로 사용해도 시간제한 안에 풀 수 있었다

 

 

---

 

문제 풀이

문제 풀이는 아래의 글을 참고했다.

[백준 - Java] 15683번 : 감시 (삼성 SW 역량 테스트 기출 문제)

 

 

1단계 : CCTV 방향 설정

CCTV 방향은 상(0), 우(1), 하(2), 좌(3) 총 4가지이다.(시계방향 순)

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

 

전체 CCTV의 설치 방향을 정하여 나올 수 있는 모든 경우의 수를 구하기 위해 순열을 이용했다. 순열은 N개의 서로 다른 값 중에 r개를 순서대로 뽑는 경우의 수이다.

 

문제에서는 0~3 (4가지 방향) 중에서 cctv 총 개수 r만큼 숫자를 순서대로 뽑아 나올 수 있는 모든 경우의 수를 구해야 했다.

이에 DFS를 활용해서 순열을 구해 cctv의 방향을 별도의 배열(cctv_direction)에 저장했다.

private static void permutation(int depth) {

        if(cctv_list.size() == depth) {
            // 1. board 새로 만들기
            copy_board = new int[board.length][board[0].length];
            for(int y=0; y<copy_board.length; y++) {
                System.arraycopy(board[y], 0, copy_board[y], 0 , board[y].length);
            }

            // 2. 표시하기
            for(int i=0; i<cctv_list.size(); i++) {
                check_cctv(cctv_list.get(i), cctv_direction[i]);
            }

            // 3. 갯수 체크
            count_section();
            return;
        }

        for(int i=0; i<4; i++) {
            cctv_direction[depth] = i;
            permutation(depth+1);
        }
    }

 

 

2단계 : 사각지대의 수 계산

우선 설정한 CCTV의 방향을 참고하여 기존 배열을 복사한 새로운 배열에 감시 가능한 구역을 표시했다.

// 자바 배열 복사 메소드
System.arraycopy(원본 배열, 원본 배열의 복사 시작 시점, 복사할 배열, 복사할 배열의 시작 시점, 복사 값 개수)

 

CCTV 종류에 따라 감시 영역을 표시했고 벽(6)을 만날 경우 감시 영역 체크를 중단했다.

private static void check_cctv(CCTV cctv, int direction) {
        if(cctv.value == 1) {
            check_board(cctv, direction);
        }else if(cctv.value == 2) {
            if(direction % 2 == 0 ) {
                check_board(cctv, 0);
                check_board(cctv, 2);
            }else {
                check_board(cctv, 1);
                check_board(cctv, 3);
            }
        }else if(cctv.value == 3) {
            check_board(cctv, direction);
            check_board(cctv, (direction+1) % 4);
        }else if(cctv.value == 4) {
            for(int i=0; i<3; i++) {
                int d = (direction + i) % 4;
                check_board(cctv, d);
            }
        }else if(cctv.value == 5) {
            check_board(cctv, 0);
            check_board(cctv, 1);
            check_board(cctv, 2);
            check_board(cctv, 3);
        }
    }
    
    private static void check_board(CCTV cctv, int direction) {
        int row = copy_board.length;
        int col = copy_board[0].length;

        int ny = cctv.y;
        int nx = cctv.x;
        while(true) {
            ny += move[direction][0];
            nx += move[direction][1];

            if(ny < 0 || ny >= row || nx < 0 || nx >= col || copy_board[ny][nx] == 6) {
                break;
            }
            
            if(copy_board[ny][nx] == 0) {
                copy_board[ny][nx] = -1;
            }
        }
    }

 

마지막으로 감시가 불가능한 영역(0) 개수를 계산했다.

private static void count_section() {
        int count = 0;
        for(int y=0; y<copy_board.length; y++) {
            for(int x=0; x<copy_board[0].length; x++) {
                if(copy_board[y][x] == 0) {
                    count += 1;
                }
            }
        }

        if(answer > count) {
            answer = count;
        }
    }

 

 

---

전체코드

 

package Implementation.baekjoon;

// 문제 : 감시
// 풀이 일자 : 2025.06.17
// 설명 : https://www.acmicpc.net/problem/15683

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

public class No_15683 {
    static int[][] move = new int[][]{{-1,0}, {0,1}, {1,0}, {0,-1}};
    static List<CCTV> cctv_list = new LinkedList<>();
    static int n, m, answer;
    static int[][] board;
    static int[][] copy_board;
    static int[] cctv_direction;

    private static class CCTV {
        int value;
        int y;
        int x;

        CCTV(int v, int y, int x) {
            this.value = v;
            this.y = y;
            this.x = x;
        }
    }

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        for(int y=0; y<n; y++) {
            st = new StringTokenizer(br.readLine());
            for(int x=0; x<m; x++) {
                board[y][x] = Integer.parseInt(st.nextToken());

                if(board[y][x] > 0 && board[y][x] < 6) {
                    cctv_list.add(new CCTV(board[y][x], y, x));
                }
            }
        }

        cctv_direction = new int[cctv_list.size()];
        answer = n*m;
        permutation(0);
        System.out.println(answer);
    }
    
    private static void permutation(int depth) {

        if(cctv_list.size() == depth) {
            // 1. board 새로 만들기
            copy_board = new int[board.length][board[0].length];
            for(int y=0; y<copy_board.length; y++) {
                System.arraycopy(board[y], 0, copy_board[y], 0 , board[y].length);
            }

            // 2. 표시하기
            for(int i=0; i<cctv_list.size(); i++) {
                check_cctv(cctv_list.get(i), cctv_direction[i]);
            }

            // 3. 갯수 체크
            count_section();
            return;
        }

        for(int i=0; i<4; i++) {
            cctv_direction[depth] = i;
            permutation(depth+1);
        }
    }

    private static void check_cctv(CCTV cctv, int direction) {
        if(cctv.value == 1) {
            check_board(cctv, direction);
        }else if(cctv.value == 2) {
            if(direction % 2 == 0 ) {
                check_board(cctv, 0);
                check_board(cctv, 2);
            }else {
                check_board(cctv, 1);
                check_board(cctv, 3);
            }
        }else if(cctv.value == 3) {
            check_board(cctv, direction);
            check_board(cctv, (direction+1) % 4);
        }else if(cctv.value == 4) {
            for(int i=0; i<3; i++) {
                int d = (direction + i) % 4;
                check_board(cctv, d);
            }
        }else if(cctv.value == 5) {
            check_board(cctv, 0);
            check_board(cctv, 1);
            check_board(cctv, 2);
            check_board(cctv, 3);
        }
    }

    private static void check_board(CCTV cctv, int direction) {
        int row = copy_board.length;
        int col = copy_board[0].length;

        int ny = cctv.y;
        int nx = cctv.x;
        while(true) {
            ny += move[direction][0];
            nx += move[direction][1];

            if(ny < 0 || ny >= row || nx < 0 || nx >= col || copy_board[ny][nx] == 6) {
                break;
            }
            
            if(copy_board[ny][nx] == 0) {
                copy_board[ny][nx] = -1;
            }
        }
    }

    private static void count_section() {
        int count = 0;
        for(int y=0; y<copy_board.length; y++) {
            for(int x=0; x<copy_board[0].length; x++) {
                if(copy_board[y][x] == 0) {
                    count += 1;
                }
            }
        }

        if(answer > count) {
            answer = count;
        }
    }
}

 

 

참고

https://minhamina.tistory.com/134

https://velog.io/@kai6666/Java-System.arraycopy-%EC%99%80Arrays.copyOf%EC%9D%98-%EC%B0%A8%EC%9D%B4-%EB%B0%B0%EC%97%B4-%EB%B3%B5%EC%82%AC