[BOJ - JAVA] 15683 - 감시 (브루트포스)

# 주소

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

15683번: 감시

# 문제

# 문제 해설 및 코드 리뷰

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main{
    static int n,m;
    static int[][] arr;
    static int zeroCount = 0;
    static List<CCTV> list;
    static int min;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,1,-1};
    static int [][][] watchDirs = {
            {},//0번타입
            {{0},{1},{2},{3}},//1번타입
            {{0,1},{2,3}},//2번타입
            {{0,2},{2,1},{1,3},{3,0}},//3번타입
            {{0,1,2},{0,1,3},{0,2,3},{1,2,3}},//4번타입
            {{0,1,2,3}}//5번타입
    };
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                arr[i][j] = scan.nextInt();
                if(arr[i][j] > 0 && arr[i][j] < 6){
                    list.add(new CCTV(i,j,arr[i][j]));
                }
                else if(arr[i][j] == 0){
                    zeroCount++;
                }
            }
        }
        min = Integer.MAX_VALUE;
        dfs(0,0);
        System.out.println(min);
    }
    static void dfs(int cctvIdx, int sum){
        if(cctvIdx == list.size()){
            min = Math.min(min, zeroCount - sum);
            return;
        }

        CCTV cctv = list.get(cctvIdx);
        for(int i = 0; i < watchDirs[cctv.t].length; i++){
            int[] ans = watchDirs[cctv.t][i];
            int scan = search(cctv, ans, -1);
            dfs(cctvIdx+1, sum + scan);
            search(cctv,ans,1);
        }
    }
    static int search(CCTV cctv, int[] ans, int flag){
        int cnt = 0;
        for(int i = 0; i < ans.length; i++){
            for(int j = 1; ; j++){
                int nx = cctv.x + dx[ans[i]] * j;
                int ny = cctv.y + dy[ans[i]] * j;
                if(!isIn(nx,ny) || arr[nx][ny] == 6){
                    break;
                }
                if(arr[nx][ny] > 0){
                    continue;
                }
                if(arr[nx][ny] == 0){
                    cnt++;
                }
                arr[nx][ny] += flag;
            }
        }
        return cnt;
    }
    static boolean isIn(int x, int y){
        return 0 <= x && 0 <= y && x < n && y < m;
    }
}
class CCTV{
    int x,y,t;
    public CCTV(int x, int y, int t){
        this.x = x;
        this.y = y;
        this.t = t;
    }
}

브루트포스는 정말 어려운 것 투성입니다.

천천히 살펴보겠습니다.

static int n,m;
static int[][] arr;
static int zeroCount = 0;
static List<CCTV> list;
static int min;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,1,-1};
static int [][][] watchDirs = {
        {},//0번타입
        {{0},{1},{2},{3}},//1번타입
        {{0,1},{2,3}},//2번타입
        {{0,2},{2,1},{1,3},{3,0}},//3번타입
        {{0,1,2},{0,1,3},{0,2,3},{1,2,3}},//4번타입
        {{0,1,2,3}}//5번타입
};

일단 n과 m을 입력받으므로 static으로 선언하였습니다.

arr의 크기는 n x m크기의 배열이 될 것입니다.

zeroCount는 0의 개수를 의미합니다.

List배열의 CCTV를 제네릭으로 받는 list를 선언하였습니다.

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

CCTV의 class내부는 다음과 같습니다.

x는 배열의 행, y는 배열의 열, t는 CCTV종류를 list에 담을 것입니다.

그리고

static int min;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,1,-1};
static int [][][] watchDirs = {
        {},//0번타입
        {{0},{1},{2},{3}},//1번타입
        {{0,1},{2,3}},//2번타입
        {{0,2},{2,1},{1,3},{3,0}},//3번타입
        {{0,1,2},{0,1,3},{0,2,3},{1,2,3}},//4번타입
        {{0,1,2,3}}//5번타입
};

min은 정답으로 입력할 값

dx와 dy는 4방향 기저를 나타낸 것이고 watchDirs는 번호별로 나타낼 수 있는 방향을 3차원으로 표현한 것입니다.

이걸 알고 계셔야합니다. 왜 watchDirs는 3차원일까요.

watchDirs는 3방향의 값을 모두 담아야하기 때문입니다.

진작에 dx와 dy방향을 매핑하는 delta의 방향을 설정할 때 2차원으로 표현하고 싶으면

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

이렇게도 표현 가능합니다.

watchDirs에서 나타내고 싶은 것은 CCTV종류의 타입별로 끊어서 값을 담는데 이를 3차원에 담으려고 한다면 다음과 같이 나타낼 수 있는 것입니다.

더 살펴봅시다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
arr = new int[n][m];
list = new ArrayList<>();
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        arr[i][j] = scan.nextInt();
        if(arr[i][j] > 0 && arr[i][j] < 6){
            list.add(new CCTV(i,j,arr[i][j]));
        }
        else if(arr[i][j] == 0){
            zeroCount++;
        }
    }
}

n과 m을 입력받고 arr의 크기를 선언합니다.

list도 ArrayList<>()로 선언하고 이중 for문으로 arr를 입력받습니다.

그리고 만약 arr[i][j]가 0보다 크고 6보다 작으면 모조리 list에 담습니다.

왜냐하면 이때의 arr값은 CCTV의 배열 인덱스를 의미하고 cctv의 종류도 담을 수 있습니다.

그리고 else if (arr가 0이라면) zeroCount를 증가시킵니다.

min = Integer.MAX_VALUE;
dfs(0,0);
System.out.println(min);

입력을 전부 다 받은 뒤 min값은 MAX_VALUE로 초기화하고 dfs(0,0)을 실행합니다.

dfs를 살펴봅시다.

static void dfs(int cctvIdx, int sum){
    if(cctvIdx == list.size()){
        min = Math.min(min, zeroCount - sum);
        return;
    }

dfs에는 cctvIdx와 sum을 파라미터로 가져옵니다.

이 때 cctvIdx가 list.size()와 같으면 return할것인데 list의 크기는 CCTV의 개수를 의미합니다.

그러므로 cctvIdx라는 변수는 탐색한 cctv의 개수를 의미합니다.

그리고 min에는 zeroCount (0의 개수) 에서 총합인 sum을 뺀 값과 기존의 min을 비교하여 작은 값을 계속 return합니다.

CCTV cctv = list.get(cctvIdx);
for(int i = 0; i < watchDirs[cctv.t].length; i++){
    int[] ans = watchDirs[cctv.t][i];
    int scan = search(cctv, ans, -1);
    dfs(cctvIdx+1, sum + scan);
    search(cctv,ans,1);
}

CCTV 클래스에서 cctv를 하나 생성하여 list에서의 cctvIdx번째의 값을 cctv에 담습니다.

그리고 for문에서 cctv의 번호에 맞는 watchDirs타입을 찾고 그것의 크기만큼 for문을 돌립니다.

만약 2번 타입이면 2번만 for문을 돌리고 3번 타입이면 4번 for문을 돌립니다.

{{0,1},{2,3}},//2번타입
{{0,2},{2,1},{1,3},{3,0}},//3번타입

이해 되시지요?

그리고 ans배열을 선언하여 watchDirs의 t타입의 i번째 값을 담습니다.

만약 2번 타입을 담으려고 한다면 제일 처음 ans[]의 값은 {0,1}, 그리고 {2,3}일 것입니다.

그 다음 scan의 값은 search함수를 실행한 값을 담는데요.

이 때 파라미터로 3가지를 담습니다.

일단 cctv와 방금 선언한 ans, 그리고 탐색한 지점은 -1만큼 빼기 위해 -1을 flag로 담습니다.

그리고 다시 dfs를 실행하여 cctvIdx+1하고 sum에는 scan값을 더합니다.

그럼 search함수는 어떻게 실행될까요?

static int search(CCTV cctv, int[] ans, int flag){
    int cnt = 0;
    for(int i = 0; i < ans.length; i++){
        for(int j = 1; ; j++){
            int nx = cctv.x + dx[ans[i]] * j;
            int ny = cctv.y + dy[ans[i]] * j;
            if(!isIn(nx,ny) || arr[nx][ny] == 6){
                break;
            }
            if(arr[nx][ny] > 0){
                continue;
            }
            if(arr[nx][ny] == 0){
                cnt++;
            }
            arr[nx][ny] += flag;
        }
    }
    return cnt;

흔히하는 bfs문과 굉장히 흡사합니다.

일단 갖고온 파라미터에 대해 int타입의 cnt를 0으로 초기화합니다.

그리고 2중 for문으로 배열을 새로 탐색할 것인데, i의 범위는 ans배열의 크기만큼 제한합니다.

만약 2번 카메라의 경우 ans의 크기는 2이므로 2번만 탐색할 것입니다.

{0,1}가 제일 처음 담길 것입니다.

그리고 그 다음 for문에서는 j=1부터 j의 크기를 따로 지정하지 않습니다.

이유는 만약 arr크기가 n x n이었으면 n으로 제한할 수 있겠지만 가로,세로 크기가 일정하지 않기 때문에 break와 continue를 통해 제한을 걸 수 있습니다. 계속 살펴봅시다.

int j = 1; ; j++){
    int nx = cctv.x + dx[ans[i]] * j;
    int ny = cctv.y + dy[ans[i]] * j;
    if(!isIn(nx,ny) || arr[nx][ny] == 6){
        break;
    }

nx와 ny를 다음과 같이 설정합니다.

가지고온 cctv에서의 현재점을 x라 하고 ans[i]는 {0,1}을 가져왔으므로 dx와 dy에서 dx[0], dy[0] = -1,0이므로 x방향으로 -1만큼씩, y방향으로 0만큼씩 탐색한 결과를 nx, ny에 담습니다.

이때 j를 곱해주는 이유는 계속해서 크기를 확장시켜 나갈 것이기 때문입니다.

그리고 1을 담아온 뒤 dx와 dy[1] 은 1,0인데 이것은 nx와 ny가 오른쪽으로 이동하겠다는 것을 의미합니다.

그래서 이번 for문에서는 좌,우로 이동하는 2번타입의 cctv탐색을 설정할 수 있습니다.

if(!isIn(nx,ny) || arr[nx][ny] == 6){
            break;
        }
        if(arr[nx][ny] > 0){
            continue;
        }
        if(arr[nx][ny] == 0){
            cnt++;
        }
        arr[nx][ny] += flag;
    }
}
return cnt;

만약 이 배열이 배열의 크기를 벗어날 때나 arr가 6일 때는 break를 하여 멈출 수 있습니다.

그리고 arr가 0보다 클 때에는 cctv의 값이므로 continue해주어야 하며 arr가 0일 때에만 cnt를 더해줍니다.

이후 arr의 값에는 flag를 더해주어 (-1) 탐색을 마칩니다.

최종적으로 cnt를 리턴하여 search문을 마치는데, 이 작업이 모두 끝난 뒤 dfs에는 sum과 scan값을 더해주어 다시 실행합니다.

그리고 search(cctv, ans, 1)을 실행하여 -1로 더해주었던 arr값을 1씩 더해주어 복원할 수 있습니다.

최종적으로 min값에는 zeroCount - sum값을 빼주어 결과적으로 가장 작은 min값을 출력하면

그것이 정답이 되겠습니다.

감사합니다.