[Algorithm] 백준 15683번(BOJ 15683) 감시 (Java)

---

안녕하세요 Coding-Knowjam입니다.

이번에 풀어볼 문제는 백준 온라인 저지 15683번 감시 문제입니다.

 

1. 문제 설명

문제를 설명하기 전에 아래에 있는 링크를 통해 문제를 읽고 와 주시길 바랍니다.

https://www.acmicpc.net/problem/15683

 

문제 풀기 위해서는 내용 그대로 구현을 하면 됩니다.

구현을 할 때 신경 써야 할 부분은 CCTV가 동서남북 방향으로 회전을 할 수 있다는 점입니다.

문제에서 테스트 케이스마다 주어지는 CCTV의 개수가 다를 텐데 이를 고려해서 모든 경우의 수를 체크해야 합니다.

예를 들어 CCTV가 2개가 주어지고, 하나가 북쪽을 바라보고 있을 때 다른 하나는 동서남북을 모두 체크해야 합니다.

이어서 서쪽을 바라볼 때도 다른 하나의 동서남북을 모두 체크해야 합니다.

이런 식이면 CCTV가 2개일 때 경우의 수는 16가지가 될 겁니다.

그러나 여기서 끝이 아니라 CCTV마다 감시 가능한 범위가 다릅니다.

만약 CCTV가 1~5번까지 모두 주어졌다면 CCTV가 바라보는 방향이 동서남북으로 바뀌는 4가지 경우에 추가적으로 해당 CCTV가 동서를 감시하는지, 동서남을 감시하는지 등 이러한 경우를 같이 고려해서 구현해야 합니다.

또한 CCTV의 개수가 많아질수록 중복으로 감시가 가능한 위치가 생기게 됩니다.

이때 앞에서 먼저 감시가 되고 있는 곳은 배제하고 체크해야 합니다.

왜냐하면 전체 사무실을 나타내는 2차원 배열을 경우의 수마다 생성하면 시간 복잡도 혹은 메모리에서 초과 판정을 받을 수 있기 때문입니다.

그러므로 하나의 2차원 배열을 계속해서 사용해야 하며, 경우의 수마다 체크를 했다가 해제했다가를 반복해줘야 합니다.

이때 앞에서 미리 감시가 가능한 곳으로 체크가 되었다면 후에 체크하는 CCTV에서는 해당 좌표를 배제해서 체크하고 해제해야 합니다.

BFS에서의 방문처리와 비슷한 개념이지만 단순히 true, false로 접근하면 앞에서 이미 감시가 된 곳도 같이 해제가 되므로 저는 CCTV마다 고유 감시 번호를 붙여주고 이를 사용해서 구분 지어줬습니다.

이러한 점을 주의해서 구현하면 어렵지 않게 풀 수 있습니다.

그럼 코드를 작성해보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingnojam.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

// 백준온라인저지 15683번 감시문제 Java풀이
public class BOJ_15683 {
    // 결과값 저장변수, 최솟값을 저장해야하므로 99999로 초기화
    static int result = 99999;

    public static void main(String[] args) throws IOException {

        // 입력정보 받을 객체
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 사무실 크기 정보 받기
        String[] mapSize = br.readLine().split(" ");

        // 사무실 세로 크기
        int N = Integer.parseInt(mapSize[0]);
        // 사무실 가로 크기
        int M = Integer.parseInt(mapSize[1]);
        // 사무실 사이즈로 배열 생성
        int[][] map = new int[N][M];

        // 사무실에 있는 cctv저장 리스트
        List<CCTV> cctvList = new ArrayList<>();

        // 사무실을 정보받아서 배열 초기화
        for (int i = 0; i < N; i++) {
            String[] mapInfo = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                int temp = Integer.parseInt(mapInfo[j]);
                map[i][j] = temp;
                // CCTV인 경우
                if (temp != 0 && temp != 6) {
                    // CCTV별로 감시하는 영역을 표시할 숫자를 다르게 생성성
                   int chkNum = Integer.parseInt("1" + String.valueOf(i) + String.valueOf(j));
                    // CCTV 생성 후 리스트에 저장
                    cctvList.add(new CCTV(temp, i, j, chkNum));
                }
            }
        }

        // CCTV감시 범위 체크를 재귀형태로 구현
        recursion(cctvList, 0, map);

        // 출력
        System.out.println(result);
    }

    // CCTV 클래스
    static class CCTV {
        // CCTV 번호
        int no;
        // CCTV의 좌표 행
        int r;
        // CCTV의 좌표 열
        int c;
        // CCTV마다 고유한 감시번호
        // 예를들어 CCTV가 감시한 곳을 # 과같은 걸로 표시하면 중복으로 감시되는 위치를 파악할 수 없음
        // 그러므로 해당 CCTV가 감시한 곳은 고유번호로 체크
        int chkNum;

        // CCTV를 생성할 때 각 변수들 초기화
        public CCTV(int no, int r, int c, int chkNum) {
            this.no = no;
            this.r = r;
            this.c = c;
            this.chkNum = chkNum;
        }
    }

    /**
     * CCTV들이 감시하는 모든 경우의 수를 체크 하기 위한 재귀메서드
     * @param cctvList : 사무실에 있는 CCTV리스트
     * @param index : CCTV리스트에 사용할 인덱스
     * @param map : 사무실을 표현한 2차원 배열
     */
    static void recursion(List<CCTV> cctvList, int index, int[][] map) {
        // 재귀메서드 진행 중 CCTV 리스트의 사이즈랑 인덱스가 같다면
        // 모든 CCTV의 방향이 정해진 상태이므로 사각지대 체크
        if(index >= cctvList.size()){
            int tempResult = 0;
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[i].length; j++) {
                    if (map[i][j] == 0) {
                        tempResult ++;
                    }
                }
            }
            // 여러가지 경우의 수 중에서 사각지대가 가장 적은 값으로 저장 후 메서드 종료
            result = Math.min(tempResult, result);
            return;
        }

        // CCTV리스트에서 CCTV가져오기
        CCTV cctv = cctvList.get(index);

        // CCTV는 동서남북 4방향으로 회전 할 수 있으므로
        // 4방향 모두 감시가능한 곳을 체크 해야함
        // 0:북, 1:서, 2:남, 3:동
        for (int d = 0; d < 4; d++) {
            // CCTV 감시가능한 곳 체크
            cctvChk(cctv.no, cctv.r, cctv.c ,d, map, cctv.chkNum);

            // 재귀메서드 실행
            // CCTV리스트에서 다음 CCTV를 꺼낼 수 있도록 인덱스 +1 증가
            recursion(cctvList, index+1, map);

            // CCTV 감시했던 곳 해제
            // 2차원 배열 1개로 계속 사용하기 위해 감시한 곳 다시 빈칸으로 변경
            // 이때, CCTV끼리 중복으로 감시가능한 곳이 있을 것이기 때문에
            // CCTV별 고유감시번호로 확인을 해서 중복난 곳을 빈칸으로 바꾸지 않도록 구현
            cctvChk(cctv.no, cctv.r, cctv.c ,d, map, cctv.chkNum);
        }
    }

    /**
     * CCTV 감시범위 체크 메서드
     * @param no : CCTV 번호
     * @param r : CCTV가 있는 행
     * @param c : CCTV가 있는 열
     * @param d : CCTV가 감시하는 방향
     * @param map : 사무실의 정보를 가진 2차원 배열
     * @param chk : CCTV별 고유 감시번호
     */
    static void cctvChk(int no, int r, int c, int d, int[][] map, int chk) {
        // 1번 CCTV인 경우
        if (no == 1) {
            // 감시 가능한 곳 체크
            chk(r, c, d, chk, map);
        }
        // 2번 CCTV인 경우
        else if (no == 2) {
            // 2번 CCTV의 경우 세로 또는 가로로 감시가 가능하므로 2가지의 방향을 모두 구함
            int D1 = d;
            int D2 = d+2 == 4 ? 0 : d+2 == 5 ? 1 : d+2;

            // 방향 별 감시 가능한 곳 체크
            chk(r, c, D1, chk, map);
            chk(r, c, D2, chk, map);
        }
        // 3번 CCTV인 경우
        else if (no == 3) {
            // 3번 CCTV의 경우 ㄱ이나 ㄴ자 형태로 감시가 가능하므로 2가지의 방향을 모두 구함
            int D1 = d;
            int D2 = d+1 == 4 ? 0 : d+1;

            // 방향 별 감시 가능한 곳 체크
            chk(r, c, D1, chk, map);
            chk(r, c, D2, chk, map);
        }
        // 4번 CCTV인 경우
        else if (no == 4) {
            // 4번 CCTV의 경우 ㅗ,ㅏ,ㅓ,ㅜ 형태로 감시가 가능하므로 3가지의 방향을 모두 구함
            int D1 = d;
            int D2 = d-1 == -1 ? 3 : d-1;
            int D3 = d+1 == 4 ? 0 : d+1;

            // 방향 별 감시 가능한 곳 체크
            chk(r, c, D1, chk, map);
            chk(r, c, D2, chk, map);
            chk(r, c, D3, chk, map);
        }
        // 5번 CCTV인 경우
        else {
            // 5번 CCTV는 동서남북 모두 감시 가능하므로 4방향 모두 체크
            // 방향을 따로 구하지 않는 이유는 모든 방향을 다 체크할 것이기 때문입니다.
            for (int i = 0; i < 4; i++) {
                // 방향 별 감시 가능한 곳 체크
                chk(r, c, i, chk, map);
            }
        }
    }

    /**
     * 감시카메라가 감시가능한 위치 감시번호로 체크하는 메서드
     * @param R : CCTV의 행
     * @param C : CCTV의 열
     * @param D : CCTV가 감시하는 방향
     * @param chkNum  : CCTV별 고유 감시번호
     * @param map  : 사무실의 정보를 가진 2차원 배열
     */
    static void chk(int R, int C, int D, int chkNum, int[][] map) {
        // 북 서 남 동으로 좌표 이동을 위해 사용할 배열
        int[] moveR = {-1, 0, 1, 0};
        int[] moveC = {0, -1, 0, 1};

        // 현재 좌표에 벽이 없는 경우
        while (map[R][C] != 6) {
            // 주어진 방향으로 이동하기 위해 좌표를 계산
            R = R + moveR[D];
            C = C + moveC[D];

            // 계산한 좌표가 배열을 벗어나는 경우는 사무실을 벗어난 것과 같음
            // 즉, 더이상 감시할 곳이 없으므로 반복문 종료
            if (R < 0 || R >= map.length || C < 0 || C >= map[0].length) {
                break;
            }else {
                // 계산한 좌표가 빈 공간인 경우 CCTV별 고유감시번호로 배열의 값 변경
                if (map[R][C] == 0) {
                    // 고유감시번호로 배열의 값을 바꾼 건 현재 해당 CCTV가 감시중이라는 뜻임
                    map[R][C] = chkNum;
                }

                // 방향을 바꿔가면서 감시 가능한 곳을 체크하고 있으므로 체크한 곳 해제를 위해 사용
                // CCTV가 서로 중복해서 감시 가능한 곳이 있을 것이기 떄문에
                // 본인이 감시한 곳만 해제하기 위해 고유감시번호로 확인합니다.
                else if (map[R][C] == chkNum) {
                    map[R][C] = 0;
                }
            }
        }
    }
}

 

작성한 코드의 라인마다 모두 주석을 달아놓았습니다.

기본적으로 모든 경우의 수를 확인하기 위해 재귀 형태로 메서드를 구현했습니다.

그리고 체크하는 로직의 경우는 CCTV번호와 방향들만 달라지고 동일한 형태를 가지기 때문에 메서드로 따로 뽑아내서 구현하였습니다.

앞에서 설명한 내용을 생각하시면서 코드를 보시면 이해하는데 어렵지 않으실 겁니다.

감사합니다.

---