[백준] 15683. 감시

문제 링크

[백준] 15683. 감시

풀이 과정

삼성 SW 역량 테스트 기출이며 시뮬레이션 문제입니다.

문제의 중요 키포인트는 다음과 같습니다.

1. 존재하는 모든 CCTV 각각에 대해 4개의 회전 방향을 고려한 모든 경우를 확인(완전 탐색)해봐야 한다.
2. $90^\circ$씩 회전하는 CCTV를 어떻게 코드로 구현할 지 생각해 봐야 한다.

1번은 각각의 CCTV의 방향을 돌린 뒤, 재귀 함수를 호출함으로써 해결했습니다.

2번은 각 CCTV의 초기 방향을 설정한 뒤, $0^\circ$ → $90^\circ$ → $180^\circ$ → $270^\circ$ 로 for 문을 돌려 방향을 재설정 해주었습니다.

static CCTV[] cctvs = new CCTV[8];
static int cctvCnt;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static int[][] dir = {
        {},
        {1},
        {1, 3},
        {0, 1},
        {0, 1, 3},
        {0, 1, 2, 3}
};

사용한 전역변수들입니다.

• cctvs : 최대 8개의 CCTV의 각 정보(좌표 & 몇 번 CCTV인지)를 보관하는 배열.
• dx, dy : 순서대로 ↑, →, ↓, ← 방향을 가리킴.
• dir : 1~5번 각 CCTV의 초기 방향. (예로, 1번은 처음에 → 방향을 보고 있음)

dfs(0, map);

맨 처음 저장된 CCTV를 가리키는 인덱스 0과 초기 입력된 지도 map 을 전달해 dfs 메소드 를 호출합니다.

static void dfs(int now, int[][] map) {
    if (now == cctvCnt) {
        calcMin(map);

        return;
    }

    int x = cctvs[now].x, y = cctvs[now].y, num = cctvs[now].num;

    for (int d = 0; d < 4; d++) {
        int[][] copied = copy(map);

        for (int i = 0; i < dir[num].length; i++) {
            int nd = (dir[num][i] + d) % 4;
            int nx = x, ny = y;

            while (true) {
                nx += dx[nd];
                ny += dy[nd];

                if (!inRange(nx, ny) || map[nx][ny] == 6) break;

                copied[nx][ny] = -1;
            }
        }

        dfs(now + 1, copied);
    }
}

dfs 메소드 는 cctvs 배열 요소 각각을 순서대로 방문합니다. 하나의 요소를 방문하면, 네 방향으로 돌려가며 감시 영역을 지도에 기록하고, 다음 요소의 인덱스와 변경된 지도로 dfs 메소드를 재귀 호출하는 동작을 수행합니다.

• CCTV의 인덱스를 의미하는 변수 now 가 cctvCnt와 같아지면, 마지막 CCTV를 방문 완료한 것이므로, 지도의 빈 칸(0) 개수를 세는 calcMin 메소드 를 호출합니다.
• 마지막 CCTV가 아니라면, 각 CCTV에 네 방향을 돌려 모든 감시 가능한 영역들을 -1로 설정해줍니다. 이는, 감시 표시입니다.
• 감시 영역 표시를 마쳤다면, 갱신된 지도와 다음 번 CCTV의 인덱스를 파라미터로 메소드를 재귀 호출합니다.

코드

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

public class Main {
    static int N, M;
    static int[][] map;
    static CCTV[] cctvs = new CCTV[8];
    static int cctvCnt;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    static int[][] dir = {
            {},
            {1},
            {1, 3},
            {0, 1},
            {0, 1, 3},
            {0, 1, 2, 3}
    };
    static int answer = 987654321;

    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());
        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < M; j++) {
                int num = Integer.parseInt(st.nextToken());
                map[i][j] = num;

                if (num == 0 || num == 6) continue;

                cctvs[cctvCnt++] = new CCTV(i, j, num);
            }
        }

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

    static void dfs(int now, int[][] map) {
        if (now == cctvCnt) {
            calcMin(map);

            return;
        }

        int x = cctvs[now].x, y = cctvs[now].y, num = cctvs[now].num;

        for (int d = 0; d < 4; d++) {
            int[][] copied = copy(map);

            for (int i = 0; i < dir[num].length; i++) {
                int nd = (dir[num][i] + d) % 4;
                int nx = x, ny = y;

                while (true) {
                    nx += dx[nd];
                    ny += dy[nd];

                    if (!inRange(nx, ny) || map[nx][ny] == 6) break;

                    copied[nx][ny] = -1;
                }
            }

            dfs(now + 1, copied);
        }
    }

    static void calcMin(int[][] copiedMap) {
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copiedMap[i][j] == 0) cnt++;
            }
        }

        answer = Math.min(answer, cnt);
    }

    static int[][] copy(int[][] arr) {
        int[][] copied = new int[N][M];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                copied[i][j] = arr[i][j];

        return copied;
    }

    static boolean inRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }

    static class CCTV {
        int x, y, num;

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