BOJ 15683 감시 [Java]

BOJ 15683 감시

1. 문제 링크

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

2. 문제 해설

백트래킹을 이용하여 cctv를 다 돌면서 cctv들의 방향에 따른 모든 조합의 경우를 다 보는 방식의 풀이를 생각했다.
방향을 어떻게 표현할 것인지가 문제였는데, 그냥 단순히 동쪽, 북쪽, 서쪽, 남쪽을 0, 1, 2, 3으로 대응시키기로 하였다.
우선 주어지는 입력에서 cctv의 위치와 타입을 저장하기위해 CCTV 클래스를 만들고 CCTV 배열을 만들어 cctv를 모두 담아주었다.
그리고 백트래킹을 이용하여 방향에 따른 모든 경우의 수를 다 살펴봐야하는데, cctv의 타입에 따라 방향의 갯수가 달라진다. cctv 타입에 대응되는 방향의 갯수를 담는 cctv_dir 배열을 만들어주었다.

백트래킹을 하는 solve 메서드를 구현해보자. 매개변수로 cctv_idx를 보내는데 이것이 의미하는 바는 cctv의 인덱스, 즉 CCTV 배열에 담겨 있는 몇 번째 cctv인가이다. 그리고 메서드 탈출은 cctv를 전부 방문하면 사각지대 갯수를 확인하고 탈출하는 방식으로 구현하였다.
cctv_idx의 cctv를 방문했으면 cctv의 방향에 맞게 감시할 수 있는 영역을 arr에 표시해줘야한다. arr에 표시해주는 메서드를 update라고 하고 구현해보자.

update 메서드는 cctv 정보와 방향 dir을 매개변수로 받는다. 111줄에서 dir%=4 처리를 해준 이유는 간단하다. update 메서드는 한 방향만을 처리하는데 cctv 타입에 따라 여러 방향을 한번에 처리해야하는 경우가 있다. 이럴 때 우리는 방향을 0, 1, 2, 3으로 표현하기로 했으므로, 대응되는 방향에 맞게 숫자를 더해주면 된다. 다만, 이렇게 더해주는 과정이 있으므로 나머지로 처리를 해줘야 일정한 값이 유지된다. 다시 update 메서드의 구현으로 돌아가면, cctv의 위치에서 매개변수로 받은 방향으로 일자로 가면서 벽을 만나기 전까지 감시 가능한 영역이라고 표시해준다. 문제에서는 #으로 표현했지만, 나는 arr를 int형으로 만들었기에 -1로 표현해주었다.

다시 solve 메서드의 구현으로 돌아가서, 이제 cctv_dir에 담겨 있는 방향 갯수만큼 돌면서 update를 해야하는데, 그 전에 arr의 원 상태를 보존해줄 tmp 배열을 만들고 arr의 내용을 담는다. 그 후, cctv 타입에 따라서 update를 해주고 다음 cctv를 방문하기 위해 solve 메서드를 재귀적으로 호출해준다. 현재 cctv에서 한 방향으로의 모든 탐색이 끝났으면 다음 방향으로 가기 전에 다시 arr를 원래대로 바꾸어주어야하므로 tmp 배열에 담아둔 내용을 다시 arr에 담는다.

시간복잡도를 한번 생각해보자. (update메서드의 호출 횟수 x update메서드의 최대 연산량 + 사각지대 확인 연산량) x 총 경우의 수 가 총 연산의 횟수가 된다. 대략의 최악의 경우를 생각해보면 8개의 cctv가 전부 4번이라고 해보자. update메서드의 호출 횟수는 3x8, update메서드의 최대 연산량은 n, m값의 최대인 8, 사각지대 확인 연산량은 nxm의 최대인 64, 총 경우의 수는 4^8이다. 그러므로 대략 최악의 연산 횟수를 계산해보면, 16777216로 넉넉하게 시간내로 통과한다.

3. 코드 보기

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static int n, m, ans;
    static int[][] arr;
    static ArrayList<CCTV> cctv = new ArrayList<CCTV>();
    static int[] cctv_dir = {4, 2, 4, 4, 1};
 
    static class CCTV {
        int r;
        int c;
        int type;
 
        public CCTV(int r, int c, int type) {
            this.r = r;
            this.c = c;
            this.type = type;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        ans = Integer.MAX_VALUE;
        arr = new int[n][m];
 
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
 
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
 
                if (arr[i][j] != 0 && arr[i][j] != 6) {
                    cctv.add(new CCTV(i, j, arr[i][j] - 1));
                }
            }
        }
 
        solve(0);
 
        bw.write(Integer.toString(ans));
        br.close();
        bw.flush();
        bw.close();
    }
 
    static void solve(int cctv_idx) {
        if (cctv_idx == cctv.size()) {
            int cnt = 0;
 
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] == 0) {
                        cnt++;
                    }
                }
            }
 
            if (cnt < ans) {
                ans = cnt;
            }
 
            return;
        }
 
        int cctv_type = cctv.get(cctv_idx).type;
        int[][] tmp = new int[n][m];
 
        for (int i = 0; i < cctv_dir[cctv_type]; i++) {
            copyArr(arr, tmp);
 
            if (cctv_type == 0) {
                update(cctv.get(cctv_idx), i);
            } else if (cctv_type == 1) {
                update(cctv.get(cctv_idx), i);
                update(cctv.get(cctv_idx), i + 2);
            } else if (cctv_type == 2) {
                update(cctv.get(cctv_idx), i);
                update(cctv.get(cctv_idx), i + 1);
            } else if (cctv_type == 3) {
                update(cctv.get(cctv_idx), i);
                update(cctv.get(cctv_idx), i + 1);
                update(cctv.get(cctv_idx), i + 2);
            } else { // cctv_type == 4
                update(cctv.get(cctv_idx), i);
                update(cctv.get(cctv_idx), i + 1);
                update(cctv.get(cctv_idx), i + 2);
                update(cctv.get(cctv_idx), i + 3);
            }
 
            solve(cctv_idx + 1);
            copyArr(tmp, arr);
        }
    }
 
    static void copyArr(int[][] from, int[][] to) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                to[i][j] = from[i][j];
            }
        }
    }
 
    static void update(CCTV tv, int dir) {
        dir %= 4;
 
        if (dir == 0) {
            for (int i = tv.c + 1; i < m; i++) {
                if (arr[tv.r][i] == 6) {
                    break;
                }
 
                arr[tv.r][i] = -1;
            }
        } else if (dir == 1) {
            for (int i = tv.r - 1; i >= 0; i--) {
                if (arr[i][tv.c] == 6) {
                    break;
                }
 
                arr[i][tv.c] = -1;
            }
        } else if (dir == 2) {
            for (int i = tv.c - 1; i >= 0; i--) {
                if (arr[tv.r][i] == 6) {
                    break;
                }
 
                arr[tv.r][i] = -1;
            }
        } else { // dir == 3
            for (int i = tv.r + 1; i < n; i++) {
                if (arr[i][tv.c] == 6) {
                    break;
                }
 
                arr[i][tv.c] = -1;
            }
        }
    }
}