[백준] 15683번 감시 (Java)

 

 

백준 15683 감시 : https://www.acmicpc.net/problem/15683

15683번: 감시

 

 

입력은 사무실의 크기와 CCTV의 종류 및 위치가 주어진다.

CCTV는 종류에 따라 감시할 수 있는 방법이 다르다. 또한 설치하는 방향에 따라 감시할 수 있는 방향도 달라진다.

 

크게 어려운 문제는 아니었지만, 구현하는 과정에 있어서 꽤나 까다로웠다.

CCTV는 상하좌우 회전이 가능하기 때문에 하나의 CCTV당 최대 4가지의 경우의 수가 나온다.

어차피 모든 CCTV의 경우의 수를 체크해봐야 하는 브루트 포스 문제이기 때문에 dfs와 bfs 중에 고민을 했는데

많이 해봤던 bfs를 사용해서 풀이를 하게 되었다.

 

우선 입력을 받을 때 빈칸인 0의 개수(num)와 CCTV의 위치(list)를 따로 변수에 저장했다.

빈칸인 0의 개수를 미리 계산해 놓아야 뒤에 CCTV 감시 구역을 채워나갈 때 1씩 줄여 나갈 수 있다.

또한 map을 조작할 때 num도 함께 컨트롤하기 위해 Node라는 클래스를 사용했다.

전체적인 흐름으로는 CCTV 감시 구역이 채워진 map을 Queue에 담으면서 bfs로 풀이했다.

 

CCTV 감시 구역을 채워나갈 때는 상하좌우를 나눠서 채워나갔다.

int[4]인 status를 사용하여 북쪽부터 시계 방향으로 index를 설정했다.

예를 들어, 아래의 그림의 status는 {0, 1, 0, 0}이고

 

아래의 그림의 status는 {1, 1, 0, 1}이다.

 

이와 같은 방식으로 모든 경우의 수 15가지에 대해서 미리 stat으로 선언을 해주었다.

status를 입력받아서 경우에 따라 상하좌우 나눠서 CCTV 감시 구역을 채워 나갔다.

 

 

또한 이번에 깨달은 점은,

배열 복사를 할 때 System.arraycopy 함수가 메모리를 적게 사용한다는 것이다. (속도는 그렇게 차이 나지 않는다...)

그동안 배열 복사를 할 때는 Arrays.copyOf 함수나 그냥 for문으로 일일이 넣었는데,

좀 더 효율성 있게 코드를 짜려면 System.arraycopy 함수를 사용해야겠다.

 

 

코드

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

public class Main {
    private static int n, m, min = 0;
    private static List<int[]> list = new ArrayList<>();
    private static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    private static int[][] stat = {
            {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1},
            {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 0},
            {0, 0, 1, 1}, {1, 0, 0, 1}, {1, 1, 1, 0}, {0, 1, 1, 1},
            {1, 0, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}
    };

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int[][] map = new int[n][m];

        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] == 0) min++;
                if (0 < map[i][j] && map[i][j] < 6) list.add(new int[]{i, j});
            }
        }

        bfs(map, min);
        System.out.println(min);
    }

    private static void bfs(int[][] map, int n) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(n, map));

        for (int i = 0; i < list.size(); i++) {
            int len = queue.size();

            for (int t = 0; t < len; t++) {
                Node m = queue.poll();
                int num = m.num;
                int x = list.get(i)[0];
                int y = list.get(i)[1];

                if (map[x][y] == 1) {
                    queue.add(cctv(m.map, x, y, num, stat[0]));
                    queue.add(cctv(m.map, x, y, num, stat[1]));
                    queue.add(cctv(m.map, x, y, num, stat[2]));
                    queue.add(cctv(m.map, x, y, num, stat[3]));
                }
                if (map[x][y] == 2) {
                    queue.add(cctv(m.map, x, y, num, stat[4]));
                    queue.add(cctv(m.map, x, y, num, stat[5]));
                }
                if (map[x][y] == 3) {
                    queue.add(cctv(m.map, x, y, num, stat[6]));
                    queue.add(cctv(m.map, x, y, num, stat[7]));
                    queue.add(cctv(m.map, x, y, num, stat[8]));
                    queue.add(cctv(m.map, x, y, num, stat[9]));
                }
                if (map[x][y] == 4) {
                    queue.add(cctv(m.map, x, y, num, stat[10]));
                    queue.add(cctv(m.map, x, y, num, stat[11]));
                    queue.add(cctv(m.map, x, y, num, stat[12]));
                    queue.add(cctv(m.map, x, y, num, stat[13]));
                }
                if (map[x][y] == 5) {
                    queue.add(cctv(m.map, x, y, num, stat[14]));
                }
            }
        }
    }

    private static Node cctv(int[][] map, int x, int y, int num, int[] status) {
        int[][] result = copy(map);

        for (int i = 0; i < 4; i++) {
            if (status[i] == 0) continue;
            int nx = x, ny = y;
            while (true) {
                nx = nx + dx[i];
                ny = ny + dy[i];

                if (!isValid(nx, ny)) break;
                if (result[nx][ny] == 6) break;

                if (result[nx][ny] == 0) {
                    result[nx][ny] = 8;
                    num--;
                }
            }
        }
        if (min > num) min = num;
        return new Node(num, result);
    }

    private static int[][] copy(int[][] map) {
        int[][] result = new int[n][m];
        for (int i = 0; i < n; i++) {
            System.arraycopy(map[i], 0, result[i], 0, m);
        }
        return result;
    }

    private static boolean isValid(int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= m) return false;
        return true;
    }
}

class Node {
    int num;
    int[][] map;

    Node(int num, int[][] map) {
        this.num = num;
        this.map = map;
    }
}