[백준] 감시

참고 : www.acmicpc.net/problem/15683

15683번: 감시

 

- 시뮬레이션 문제

- 90도씩 돌아가면서 보이는 곳에 마킹을 해줌

- 마킹 안 되어 있는 곳 (cctv, 벽 제외) 의 최소값을 구해줌.

 

 

import java.util.*;

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

    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static int[][] board1 = new int[10][10];
    private static int[][] board2 = new int[10][10];
    private static List<CCTV> cctv = new ArrayList<>();

    private static boolean oob(int a, int b, int n, int m) {
        return a < 0 || a >= n || b < 0 || b >= m;
    }

    private static void upd(int x, int y, int dir, int n, int m) {
        dir %= 4;
        while(true) {
            x += dx[dir];
            y += dy[dir];
            if(oob(x, y, n, m) || board2[x][y] == 6) return;
            if(board2[x][y] != 0) continue;
            board2[x][y] = 7;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int mn = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board1[i][j] = sc.nextInt();
                if(board1[i][j] != 0 && board1[i][j] != 6) {
                    cctv.add(new CCTV(i, j));
                }
                if(board1[i][j] == 0) mn++;
            }
        }

        System.out.println("cctv size : " + cctv.size());
        System.out.println("cctv size2 : " + (1<<(2*cctv.size())));
        for (int tmp = 0; tmp < (1<<(2*cctv.size())); tmp++) {
            System.out.println("tmp" + tmp);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    board2[i][j] = board1[i][j];
                }
            }
            int brute = tmp;
            for (int i = 0; i < cctv.size(); i++) {
                int dir = brute % 4;
                brute /= 4;
                int x = cctv.get(i).x;
                int y = cctv.get(i).y;
                if(board1[x][y] == 1) {
                    upd(x, y, dir, n, m);
                }
                else if(board1[x][y] == 2) {
                    upd(x, y, dir, n, m);
                    upd(x, y, dir+2, n, m);
                }
                else if(board1[x][y] == 3) {
                    upd(x, y, dir, n, m);
                    upd(x, y, dir+1, n, m);
                }
                else if(board1[x][y] == 4) {
                    upd(x, y, dir, n, m);
                    upd(x, y, dir+1, n, m);
                    upd(x, y, dir+2, n, m);
                }
                else {
                    upd(x, y, dir, n, m);
                    upd(x, y, dir+1, n, m);
                    upd(x, y, dir+2, n, m);
                    upd(x, y, dir+3, n, m);
                }
            }
            int val = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (board2[i][j]==0) val += 1;
                }
            }
            mn = Math.min(mn, val);
        }
        System.out.println(mn);
    }
}