[백준 JAVA] 15683번: 감시

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

.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int N, M, ans = 100, cnt = 0;
    public static int[][] map, copyMap;
    public static int[][] cctv, cctv2;
    public static int[] arr;
    public static int[] dx = { -1, 0, 1, 0 };
    public static int[] dy = { 0, 1, 0, -1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 1. 입력받기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 1-1. map, copyMap 만들기
        map = new int[N][M];
        copyMap = new int[N][M];
        cctv = new int[10][3];
        cctv2 = new int[10][3];
        int cnt2 = 0;
        // 1-2. map 입력 받기
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 5) {
                    cctv2[cnt2][0] = i;
                    cctv2[cnt2][1] = j;
                    cctv2[cnt2][2] = map[i][j];
                    cnt2++;
                } else if (map[i][j] > 0 && map[i][j] < 6) {
                    cctv[cnt][0] = i;
                    cctv[cnt][1] = j;
                    cctv[cnt][2] = map[i][j];
                    cnt++;
                }
            }
        }

        for (int i = 0; i < cnt2; i++) {

            int x = cctv2[i][0];
            int y = cctv2[i][1];

            bfs(map, x, y, 0);
            bfs(map, x, y, 1);
            bfs(map, x, y, 2);
            bfs(map, x, y, 3);
        }

        arr = new int[cnt];

        dfs(0);

        System.out.println(ans);

    }

    public static void dfs(int depth) {
        if (depth == cnt) {

            copy();
            for (int i = 0; i < cnt; i++) {
                int x = cctv[i][0];
                int y = cctv[i][1];
                int mod = cctv[i][2];

                if(mod == 1) {
                    bfs(copyMap, x, y, arr[i]);
                } else if(mod == 2) {
                    bfs(copyMap, x, y, arr[i]);
                    bfs(copyMap, x, y, (arr[i] + 2) %4);
                } else if(mod == 3) {
                    bfs(copyMap, x, y, arr[i]);
                    bfs(copyMap, x, y, (arr[i] + 1) %4);
                } else if(mod == 4) {
                    bfs(copyMap, x, y, arr[i]);
                    bfs(copyMap, x, y, (arr[i] + 1) %4);
                    bfs(copyMap, x, y, (arr[i] + 2) %4);
                }

            }


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

            if(zero < ans) {
                ans = zero;
            }

            return;
        }

        for (int i = 0; i < 4; i++) {
            if (cctv[depth][2] == 2 && (i == 2 || i == 3))
                continue;

            arr[depth] = i;
            dfs(depth + 1);
        }
    }

    private static void bfs(int[][] map, int x, int y, int dis) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { x, y });
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int nx = cur[0] + dx[dis];
            int ny = cur[1] + dy[dis];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;
            if (map[nx][ny] != 6) {
                map[nx][ny] = 7;
                q.offer(new int[] { nx, ny });
            }
        }
    }

    public static void copy() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copyMap[i][j] = map[i][j];
            }
        }
    }

}

 

풀이 사항
풀이 일자: 2024.08.29
풀이 시간: 40분 00초
채점 결과: 정답
예상 문제 유형: DFS, BFS

 

풀이 방법

1. CCTV의 최대 개수가 8개를 넘지 않고 사무실의 크기 또한 64를 넘지 않았기 때문에 완전탐색으로 문제를 풀 수 있을것이라고 생각하고 DFS의 중복순열을 통해 CCTV감시 방향을 정해주엇다.

 

2. map값을 받아옴과 동시에 CCTV의 위치와 종류를 배열에 저장해주었다.

 

3. CCTV 5의 경우에는 어떤상황에서도 4방을 감시하기 때문에 CCTV 배열을 따로 관리해주고 맵에 감시 범위를 미리 채운 뒤 DFS탐색에 포함시키지 않았다 .

 

4. 또한 CCTV 2의 경우에는 방향이 두방향밬에 없으므로 0과 1의 값만 가질 수 있게 if문을 설정해주었다. 이 부분은 그냥 4방향 다 뽑고 02면 가로 13이면 세로 이런식으로 구현해도 될꺼같다.

 

5. 각각의 DFS 결과 마다 map을 수정하고 원복해야 하므로 copyMap과 copy메서드를 사용해서 구현했고 BFS에서 좌표, 방향을 받아 copyMap의 감시 범위를 채워준다.

 

6. 각 CCTV의 종류마다 감시범위를 다르게 설정해서 BFS를 진행해주었고 다 끝났다면 ans와 비교해서 최소값을 출력해준다.

 

맵을 채우는 BFS과정에서 0일때만 맵을 채워주고 큐에 좌표를 넣어줬는데 이렇게 하면 감시범위가 겹치는 경우에 그 뒤까지 더이상 탐색을 진행하지 않아 오답이 나오게 되었다. 따라서 벽이 아닌경우에는 무조건 채우고 벽으로 채우는게 아닌 다른 값으로 채워주었다. CCTV의 좌표는 이미 가지고 있으므로 맵에서 CCTV가 사라지는것을 두려워하지 않아도 된다.