이번에 풀어본 문제는
백준 15683번 감시 입니다.

📕 문제 링크

❗️코드

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

class Cam
{
    int num,x,y;

    public Cam(int num, int x, int y)
    {
        this.num = num;
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int N,M;
    static int MIN = Integer.MAX_VALUE;
    static int [][] map;
    static List<Cam> tv_loc;
    static List<String> [] input_list;
    static List<String> scanList;
    static int [] dx = {-1,0,1,0};
    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());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        tv_loc = new ArrayList<>();

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

        if(tv_loc.isEmpty()) // cctv가 없을 때
        {
            int MIN = N * M;
            for(int [] i : map)
            {
                for(int j : i)
                {
                    if(j > 0) MIN--;
                }
            }
            System.out.print(MIN);
            return;
        }

        String [] mv_list  = {"","0 1 2 3","13 02","01 12 23 30","013 012 123 023","0123"};
        int input_size = tv_loc.size();

        input_list = new List[input_size];
        for(int i = 0; i < input_size; ++i) input_list[i] = new ArrayList<>();

        for(int i = 0; i < input_size; ++i)
        {
            st = new StringTokenizer(mv_list[tv_loc.get(i).num]);
            while(st.hasMoreTokens())
            {
                input_list[i].add(st.nextToken());
            }
        }

        scanList = new ArrayList<>();
        comb("",0);

        int [][] copy_map = new int[N][M];
        for(String comb : scanList)
        {
            String [] mv = comb.split(" ");
            for(int i = 0; i < N; ++i)
            {
                System.arraycopy(map[i],0,copy_map[i],0,M);
            }
            int scan_cnt = 0;
            for(int i = 0; i < mv.length; ++i)
            {
                Cam cur = tv_loc.get(i);
                char [] mv_arr = mv[i].toCharArray();

                for(int dir : mv_arr)
                {
                    scan_cnt += move(cur,dir-'0',copy_map,0);
                }
            }
            MIN = Math.min(MIN,zero_cnt-scan_cnt);
        }

        System.out.print(MIN);
    }
    static void comb(String comb,int depth) {
        if(depth == input_list.length)
        {
            scanList.add(comb);
            return;
        }

        int size = input_list[depth].size();
        for(int i = 0; i < size; ++i)
        {
            comb(comb+input_list[depth].get(i)+" ",depth+1);
        }
    }
    static int move(Cam cam,int dir, int [][] copy_map,int scan_cnt)
    {
        int x = cam.x;
        int y = cam.y;
        int cnt = scan_cnt;
        while(true)
        {
            x += dx[dir];
            y += dy[dir];
            if(!isValid(x,y) || copy_map[x][y] == 6) break;
            if(copy_map[x][y] > 0 && copy_map[x][y] < 6) continue;
            else
            {
                if(copy_map[x][y] == -1) continue;
                copy_map[x][y] = -1;
                cnt++;
            }
        }
        return cnt;
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}

📝 풀이

설치된 cctv의 각도를 변경하여 주어진 입력에서 사각지대를 최소로 만들 수 있는 경우의 수를 구하는 문제입니다.
모든 경우의 수를 구하기 위해, 우선 각 cctv의 번호별로 감시할 수 있는 방향을
0 - 상 / 1 - 우 / 2 - 하 / 3 - 좌 를 인덱스로 갖는 dx,dy 배열을 만들었고, 해당 방향을 전달인자로 함수를 호출하여, 벽을 만나거나 범위를 벗어날때 까지 위치를 이동해 주었습니다.
사각지대는 전처리 과정에서 0의 총 갯수를 카운트 한 후, 경우의 수 마다 지워지는 0의 개수를 따로 카운트하여 두 값을 빼주었습니다. 한번 방문한 곳은 -1로 변경해주어 따로 방문배열을 만들지 않았습니다.

📜 후기

앞으로는 구현문제 위주로 풀 계획입니다.