[알고리즘/백준] 15683 감시 - 자바(Java), 삼성 SW 역량테스트

문제

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

풀이 코드

1. DFS를 사용하여 CCTV들 방향의 모든 조합을 구한다.
2. 각 경우의 수 마다 사각지대 개수를 구하여 최소 사각지대 개수를 구한다.

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

import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static class CCTV {
        int type;
        int x;
        int y;

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

    static List<CCTV> cctvs;
    static int[][] board, copyBoard;
    static int[] directions;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int numOfCCTV, n, m;
    static int min = Integer.MAX_VALUE;

    private static void dfs(int level) {
        if(level == numOfCCTV) {
            copyBoard();

            for (int i = 0; i < numOfCCTV; i++) {
                int d = directions[i];
                CCTV cctv = cctvs.get(i);

                observeCCTV(d, cctv);
            }

            checkSquareArea();

        } else {
            for (int i = 0; i < 4; i++) {
                directions[level] = i;
                dfs(level+1);
            }
        }
    }

    /**
     * cctv의 감시 방향이 d일 때 각 cctv의 방향 개수에 맞추어 감시
     */
    private static void observeCCTV(int d, CCTV cctv) {
        if (cctv.type == 1) {
            observeDirection(cctv, d);
        } else if (cctv.type == 2) {
            if (d == 0 || d == 2) {
                observeDirection(cctv, 0);
                observeDirection(cctv, 2);
            } else {
                observeDirection(cctv, 1);
                observeDirection(cctv, 3);
            }
        } else if (cctv.type == 3) {
            if (d == 3) {
                observeDirection(cctv, 0);
                observeDirection(cctv, 3);
            } else {
                observeDirection(cctv, d);
                observeDirection(cctv, d +1);
            }
        } else if (cctv.type == 4) {
            if (d == 0) {
                observeDirection(cctv, 0);
                observeDirection(cctv, 1);
                observeDirection(cctv, 3);
            } else if (d == 1) {
                observeDirection(cctv, 0);
                observeDirection(cctv, 1);
                observeDirection(cctv, 2);
            } else if(d == 2) {
                observeDirection(cctv, 1);
                observeDirection(cctv, 2);
                observeDirection(cctv, 3);
            } else if (d == 3) {
                observeDirection(cctv, 2);
                observeDirection(cctv, 3);
                observeDirection(cctv, 0);
            }
        } else if (cctv.type == 5) {
            observeDirection(cctv, 0);
            observeDirection(cctv, 1);
            observeDirection(cctv, 2);
            observeDirection(cctv, 3);
        }
    }

    /**
     * cctv를 direction 방향으로 감시한다.
     * @param direction 0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽
     */
    private static void observeDirection(CCTV cctv, int direction) {
        int nx = cctv.x + dx[direction];
        int ny = cctv.y + dy[direction];

        while(nx >= 0 && nx < n && ny >= 0 && ny < m && copyBoard[nx][ny] != 6) {
            copyBoard[nx][ny] = -1;

            nx += dx[direction];
            ny += dy[direction];
        }
    }

    /**
     * 사각지대의 개수를 구한다.
     */
    private static void checkSquareArea() {
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyBoard[i][j] == 0) {
                    count++;
                }
            }
        }

        min = Math.min(min, count);
    }

    private static void copyBoard() {
        copyBoard = new int[n][m];

        for (int i = 0; i < n; i++) {
            System.arraycopy(board[i], 0, copyBoard[i], 0, m);
        }
    }

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

        cctvs = 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] >= 1 && board[i][j] <= 5) {
                    cctvs.add(new CCTV(board[i][j], i, j));
                }
            }
        }

        directions = new int[cctvs.size()];
        numOfCCTV = cctvs.size();

        dfs(0);

        System.out.println(min);
    }
}