백준 감시

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다.
0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.

첫째 줄에 사각 지대의 최소 크기를 출력한다.

내가 이 문제를 보고 생각해본 부분

main에서 입력을 받고 CCTV 리스트를 만든다.
각 CCTV의 가능 방향 조합을 directions 배열로 미리 정의해 둔다.
dfs는 백트래킹 함수로 CCTV 하나씩 방향 조합을 정하고 감시 영역을 표시하는 작업을 한다.
모든 CCTV 방향을 정하면 getBlindSpotCount로 사각지대를 계산해 최소값을 갱신해준다.
copyArray함수로 현재 상태를 복사해서 함부로 원본을 건드리지 않고 재귀 탐색한다.
watch 함수는 한 방향으로 벽을 만날 때까지 감시 표시를 한다.
사각지대는 0으로 남은 칸의 개수이며 최소가 답이다.

코드로 구현

package baekjoon.baekjoon_33;

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

// 백준 15683번 문제
public class Main1327 {
    static int N, M;
    static int[][] map;
    static ArrayList<int[]> cctvList = new ArrayList<>();
    static int[] dx = { -1, 0, 1, 0 }; // 상, 우, 하, 좌
    static int[] dy = { 0, 1, 0, -1 };
    static int answer = Integer.MAX_VALUE;
    // CCTV별 감시 방향 조합(방향 인덱스 기준)
    static int[][][] directions = {
            {}, // 인덱스 맞추기 위해 비워둠
            { {0}, {1}, {2}, {3} }, // 1번 CCTV
            { {0, 2}, {1, 3} }, // 2번 CCTV (상-하, 좌-우)
            { {0, 1}, {1, 2}, {2, 3}, {3, 0} }, // 3번 CCTV (직각 방향)
            { {0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1} }, // 4번 CCTV (3방향)
            { {0, 1, 2, 3} } // 5번 CCTV (4방향)
    };

    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];

        // 입력받으면서 CCTV 위치 기록
        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());
                if(map[i][j] >= 1 && map[i][j] <= 5){
                    cctvList.add(new int[]{i,j,map[i][j]});
                }
            }
        }

        dfs(0, map);
        System.out.println(answer);
        br.close();
    }

    // 깊이 우선 탐색: cctvIndex 번째 CCTV 방향 정하기
    static void dfs(int cctvIndex, int[][] arr){
        if(cctvIndex == cctvList.size()){
            // 모든 CCTV 방향 정했으면 사각지대 크기 계산
            int blindSpot = getBlindSpotCount(arr);
            answer = Math.min(answer, blindSpot);
            return;
        }

        int[] cctv = cctvList.get(cctvIndex);
        int x = cctv[0];
        int y = cctv[1];
        int type = cctv[2];

        for(int i=0; i<directions[type].length; i++){
            int[][] temp = copyArray(arr);
            for(int dir : directions[type][i]){
                watch(temp, x, y, dir);
            }
            dfs(cctvIndex + 1, temp);
        }
    }

    // 배열 복사
    static int[][] copyArray(int[][] origin){
        int[][] copy = new int[N][M];
        for(int i = 0; i < N; i++){
            System.arraycopy(origin[i], 0, copy[i], 0, M);
        }
        return copy;
    }

    // 감시 영역 표시 (# 대신 7로 표시)
    static void watch(int[][] arr, int x, int y, int dir){
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        while(nx >= 0 && ny >= 0 && nx < N && ny < M){
            if(arr[nx][ny] == 6)
                break; // 벽이면 중단
            if(arr[nx][ny] == 0){
                arr[nx][ny] = 7; // 감시 영역 표시
            }
            nx += dx[dir];
            ny += dy[dir];
        }
    }

    // 사각지대 (0) 개수 계산
    static int getBlindSpotCount(int[][] arr){
        int count = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(arr[i][j] == 0)
                    count++;
            }
        }
        return count;
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.