15683. 감시

문제 개요

최대 8개의 CCTV의 방향을 바꾸어가면서 가장 많은 지역을 감시할 수 있는 방법을 찾는 문제입니다.

문제 접근

최대 8개의 CCTV가 존재하고 4방향으로만 돌릴 수 있으므로 최대 4⁸=65,536 번의 시도가 있어야 합니다. 따라서 최대 시도 횟수가 적으므로 브루트포스로 해결할 수 있습니다.

그래서 백트래킹과 일부 구현을 통해 문제를 해결하였습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Camera{
    private int row;
    private int col;
    private int dir;
    private int various;
    static final int[][] moves = {
        {0, 1},
        {1, 0},
        {0 ,-1},
        {-1 ,0}
    };

    public Camera(int row, int col, int various){
        this.row = row;
        this.col = col;
        this.dir = 0;
        this.various = various;
    }

    public int getRow() {
        return row;
    }
    public void setRow(int row) {
        this.row = row;
    }
    public int getCol() {
        return col;
    }
    public void setCol(int col) {
        this.col = col;
    }
    public int getDir() {
        return dir;
    }
    public void setDir(int dir) {
        this.dir = dir;
    }
    public int getVarious() {
        return various;
    }
    public void setVarious(int various) {
        this.various = various;
    }
    public void rotate(){
        dir = (dir + 1) % 4;
    }
}

public class Main {
    static int N;
    static int M;
    static int[][] office;

    static void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] sizes = bf.readLine().split(" ");
        N = Integer.parseInt(sizes[0]);
        M = Integer.parseInt(sizes[1]);
        office = new int[N][];

        for(int i=0;i<N;i++){
            office[i] = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
    }

    static boolean isOk(int row, int col, int dir){
        int nextRow = row + Camera.moves[dir][0];
        int nextCol = col + Camera.moves[dir][1];
        if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M){
            return false;
        }
        return office[nextRow][nextCol] != 6;
    }

    static int extend(int row, int col, int dir, boolean[][] isChecked){
        int tiles = 0;
        while(isOk(row, col, dir)){
            row += Camera.moves[dir][0];
            col += Camera.moves[dir][1];
            if(isChecked[row][col]){
                continue;
            }
            if(office[row][col]>0){
                continue;
            }
            tiles++;
            isChecked[row][col] = true;
        }
        return tiles;
    }

    static int watchingTiles(Camera camera, boolean[][] isChecked){
        int various = camera.getVarious();
        int tiles = 0;
        tiles += extend(camera.getRow(), camera.getCol(), camera.getDir(), isChecked);
        if(various == 2){
            return tiles + extend(camera.getRow(), camera.getCol(), (camera.getDir()+2)%4, isChecked);
        }
        if(various > 2){
            tiles += extend(camera.getRow(), camera.getCol(), (camera.getDir()+1)%4, isChecked);
        }
        if(various > 3){
            tiles += extend(camera.getRow(), camera.getCol(), (camera.getDir()+2)%4, isChecked);
        }
        if(various > 4){
            tiles += extend(camera.getRow(), camera.getCol(), (camera.getDir()+3)%4, isChecked);
        }
        return tiles;
    }

    static int getWatched(List<Camera> cameras){
        boolean[][] isChecked = new boolean[N][M];
        int tiles = 0;
        for(var camera : cameras){
            tiles += watchingTiles(camera, isChecked);
        }
        return tiles;
    }

    static int tracking(List<Camera> cameras, int n){
        if(n < cameras.size()){
            int tiles = 0;
            for(int i=0;i<4;i++){
                cameras.get(n).rotate();
                tiles = Math.max(tracking(cameras, n+1), tiles);
            }
            return tiles;
        }
        return getWatched(cameras);
    }

    static void process() {
        List<Camera> cameras = new ArrayList<>();
        int tiles = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(office[i][j] == 0){
                    tiles++;
                    continue;
                }
                if(office[i][j] == 6){
                    continue;
                }
                cameras.add(new Camera(i, j, office[i][j]));
            }
        }

        System.out.println(tiles - tracking(cameras, 0));
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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