[백준] Gold III. 감시

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

 

사용 알고리즘

• DFS
• 백트래킹

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m;
    static int [][] board;
    static int total = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        List<CCTV> cctv = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] != 0 && board[i][j] != 6) { // CCTV를 찾았을 때
                    cctv.add(new CCTV(board[i][j], i, j));
                }
            }
        }

        dfs(0, board, cctv);
        System.out.println(total);
    }

    public static void dfs(int depth, int[][] board, List<CCTV> cctv) {
        if (depth == cctv.size()) { // cctv 모든 부분을 돌았을 때
            total = Math.min(total, count(board));
            return;
        }

        int type = cctv.get(depth).type;
        int x = cctv.get(depth).x;
        int y = cctv.get(depth).y;

        int [][] temp;
        if (type == 1) {
            temp = copy(board);
            checkRight(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkLeft(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkUp(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkDown(temp, x, y);
            dfs(depth + 1, temp, cctv);
        }

        else if (type == 2) {
            temp = copy(board);
            checkLeft(temp, x, y);
            checkRight(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkUp(temp, x, y);
            checkDown(temp, x, y);
            dfs(depth + 1, temp, cctv);
        }

        else if (type == 3) {
            temp = copy(board);
            checkUp(temp, x, y);
            checkRight(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkRight(temp, x, y);
            checkDown(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkDown(temp, x, y);
            checkLeft(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkLeft(temp, x, y);
            checkUp(temp, x, y);
            dfs(depth + 1, temp, cctv);
        }

        else if (type == 4) {
            temp = copy(board);
            checkLeft(temp, x, y);
            checkUp(temp, x, y);
            checkRight(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkUp(temp, x, y);
            checkRight(temp, x, y);
            checkDown(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkRight(temp, x, y);
            checkDown(temp, x, y);
            checkLeft(temp, x, y);
            dfs(depth + 1, temp, cctv);

            temp = copy(board);
            checkDown(temp, x, y);
            checkLeft(temp, x, y);
            checkUp(temp, x, y);
            dfs(depth + 1, temp, cctv);
        }

        else if (type == 5) {
            temp = copy(board);
            checkUp(temp, x, y);
            checkRight(temp, x, y);
            checkDown(temp, x, y);
            checkLeft(temp, x, y);
            dfs(depth + 1, temp, cctv);
        }
    }

    public static void checkRight(int [][] temp, int x, int y) {
        for(int i = y + 1; i < m; i++) {
            if (temp[x][i] == 6) return; // 벽이 있는 경우 지나갈 수 없음. -> continue로 착각
            if (temp[x][i] == 0) temp[x][i] = -1;
        }
    }

    public static void checkLeft(int [][] temp, int x, int y) {
        for(int i = y - 1; i >= 0; i--) { // -> i 대신 y넣어서 실수...
            if (temp[x][i] == 6) return; // 벽이 있는 경우 지나갈 수 없음.
            if (temp[x][i] == 0) temp[x][i] = -1;
        }
    }

    public static void checkUp(int [][] temp, int x, int y) {
        for(int i = x - 1; i >= 0; i--) {
            if (temp[i][y] == 6) return;
            if (temp[i][y] == 0) temp[i][y] = -1;
        }
    }

    public static void checkDown(int [][] temp, int x, int y) {
        for(int i = x + 1; i < n; i++) {
            if (temp[i][y] == 6) return;
            if (temp[i][y] == 0) temp[i][y] = -1;
        }
    }
    public static int[][] copy(int [][] board) {
        int [][] temp = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                temp[i][j] = board[i][j];
            }
        }
        return temp;
    }


    public static int count(int [][] temp) {
        int count = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (temp[i][j] == 0) count++;
            }
        }
        return count;
    }

    static class CCTV {
        int type;
        int x;
        int y;
        CCTV(int type, int x, int y) {
            this.type = type;
            this.x = x;
            this.y = y;
        }
    }
}

 

회고

 

각 CCTV가 볼 수 있는 방향의 최댓값은 4이고, CCTV의 최대 개수는 8개 이므로 최악의 케이스인 경우 4^8 = 65536 가짓 수가 나온다.

CCTV의 정보들을 어떻게 저장할 것인가?

• CCTV 클래스를 만들어서 타입과, 좌표 정보를 저장

각 CCTV가 감시하는 경우는 어떻게 되는가?

1번 같은 경우 모든 방향으로 4번 동작을 수행하고, 2번은 좌우 / 상하 2번, 3번은 4번, 4번도 4번, 그리고 마지막 5번은 1번만 동작을 수행하게 된다. 각 방향으로 돌면서 영역 표시를 하고, 모든 방향으로 돌았을 때는 다음 재귀함수를 호출한다. 

 

depth == cctv.size() 처럼 모든 종류의 cctv에 대해 탐색이 마무리 된 경우, 리턴하여 다시 다음 방향을 돈다.

 

배열 복사는 어떻게?

int [][] temp = new int[n][m];

public static void copy(int [][] temp) {
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            temp[i][j] = board[i][j];
        }
    }
}

...
copy(temp);
checkRight(temp, x, y);
dfs(depth + 1, board, cctv);

 

기존에는 이런 식으로 배열 복사를 진행했었다. 하지만, 이런식으로 풀이를 진행하면 temp 배열을 초기화하지 않기 때문에 이전 상태가 남아있어서 문제가 된다. 결국 재사용이 문제인 것이다! 

 

int[][] temp = copy(board);
checkRight(temp, x, y);
dfs(depth + 1, temp, cctv);

 

그래서 이렇게 매번 temp 배열을 초기화 해줘야 원하는 답을 구할 수 있다.

 

처음에 CCTV 정보를 어떻게 저장할 것인지, 백트래킹은 어떻게 돌려줄지 감이 안왔지만 풀이를 보다보니 이해가 어느정도 됐다.

 

이번 문제에서 배워야 될 부분은 CCTV 클래스를 선언해서 더 간편하게 정보를 저장하는 것과, 주어진 요구사항에 맞게 좌,우,상,하를 체크하는 클래스들을 만들어 잘게 쪼개 생각하는 능력이 필요할 것 같다.