[백준] 15683 감시 - Brute Force / Java

• 문제 링크

15683번: 감시

 

• 풀이 과정

크기가 n * m 인 2차원 배열 map 에 cctv 및 벽의 정보를 입력받고,

cctv 의 좌표(y, x) 와 해당 cctv 의 종류(type) 및 감시 가능 방향(dir)을

제네릭이 Node 클래스인 List 객체 list 에 저장한다.

 

이때 n * m 에 cctv 의 개수와 벽의 개수를 뺀 값이 사각지대의 개수의 초기값이 되며,

해당 값을 cnt, list 에서 cctv 정보를 가져올 인덱스 값을 idx, 탐색할 2차원 배열을 map 을 매개 변수로

재귀 함수 recur 에 전달 및 실행한다.

 

각각의 cctv 마다 90도씩 회전할 때 해당 방향을 감시하기 전의 map 배열의 값을 copy 배열에 복사해두고,

cctv 의 정보가 저장된 Node 객체 cam 에서 해당 cctv의 좌표 및 감시 가능한 방향를 꺼내어

operate 함수에 매개 변수로 전달 및 실행한다.

 

이때 해당 cctv 의 좌표를 기준으로 상하좌우 중 감시 가능한 방향으로 탐색하며

cctv 및 이미 탐색한 영역은 건너뛴다.

배열의 범위를 벗어나거나 벽이 존재할 경우,

해당 방향으로 모든 탐색을 끝냈으므로 탐색한 공간의 개수를 반환한다.

 

현재까지의 사각지대의 수에서 operate 에서 반환한 값을 뺀 값을 재귀 함수에 매개 변수로 전달 및 호출하며,

해당 cctv 의 90도 회전한 다른 경우를 확인하기 위해

기존에 복사해두었던 copy 배열을 활용하여 map 배열을 원상복귀한다.

 

idx == list.size(), 즉 모든 cctv 의 경우의 수를 확인하였을 때,

min값을 구해진 cnt 값과 비교해 최소값으로 갱신시켜 최종적으로 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int n, m;
    static int min = Integer.MAX_VALUE;
    static List<Node> list = new ArrayList<>();
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

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

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

        int total = 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] == 1)
                    list.add(new Node(i, j, 1, new int[][]{{1}, {2}, {3}, {0}}));
                if (map[i][j] == 2)
                    list.add(new Node(i, j, 2, new int[][]{{1, 3}, {0, 2}}));
                if (map[i][j] == 3)
                    list.add(new Node(i, j, 3, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 0}}));
                if (map[i][j] == 4)
                    list.add(new Node(i, j, 4, new int[][]{{0, 1, 3}, {0, 1, 2}, {1, 2, 3}, {2, 3, 0}}));
                if (map[i][j] == 5)
                    list.add(new Node(i, j, 5, new int[][]{{0, 1, 2, 3}}));
                if (map[i][j] == 6)
                    total--;
            }
        }

        recur(total - list.size(), 0, map);

        bw.write(min + "\n");
        bw.flush();
    }

    private static void recur(int cnt, int idx, int[][] map) {
        if (idx == list.size()) {
            min = Math.min(min, cnt);
            return;
        }

        int[][] copy = new int[n][m];
        copy(copy, map);

        Node cam = list.get(idx);
        for (int i = 0; i < cam.dir.length; i++) {
            int observe = 0;
            for (int j = 0; j < cam.dir[i].length; j++)
                observe += operate(cam.y, cam.x, cam.dir[i][j], map);

            recur(cnt - observe, idx + 1, map);
            copy(map, copy);
        }
    }

    private static int operate(int y, int x, int dir, int[][] map) {
        int cnt = 0;

        while (true) {
            y += dy[dir];
            x += dx[dir];

            if (y < 0 || x < 0 || y >= n || x >= m || map[y][x] == 6)
                return cnt;
            if (map[y][x] >= 1 && map[y][x] <= 5 || map[y][x] == -1)
                continue;

            map[y][x] = -1;
            cnt++;
        }
    }

    private static void copy(int[][] copy, int[][] map) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                copy[i][j] = map[i][j];
        }
    }

    private static class Node {
        int y, x, type;
        int[][] dir;

        public Node(int y, int x, int type, int[][] dir) {
            this.y = y;
            this.x = x;
            this.type = type;
            this.dir = dir;
        }
    }

}