구현 문제

간단하게 말해서 5가지의 CCTV 종류를 통해 감시 할 수 없는 지역이 가장 적은 경우의 수를 구해야 한다.

1번 CCTV 의 경우 좌 , 우 , 상 , 하 중 1 가지의 방향
2번 CCTV 의 경우 좌우 , 상하 중 1가지 ,
3번 CCTV 의 경우 상우 , 하좌 , 상좌 , 하우 4가지 중 1가지 ,
4번 CCTV 의 경우 상좌우 , 하좌우 , 상우하 , 상좌하 4가지 중 1가지,
5번 CCTV 의 경우 상하좌우 1가지

위와 같은 경우의 수를 모두 고려해야 한다.

여기서 문제에 사용된 알고리즘은 재귀 함수정도 있다.

먼저 경우의 수를 구해야 한다!

총 경우의 수는 CCTV가 어느 방향을 볼지에 따라 다른데 예를 들어보자면

1번부터 5번까지 골고루 한 가지씩 있다고 가정해보면
4 2 4 4 1 의 모든 경우의 수를 가정해야 답이 나온다. 최소값을 구해야 함으로!

코드를 살펴보자.

public class Main {
   public static int N, M;
   public static int[][] map;
   public static int[][] copyMap;
   public static int[] output;
   public static ArrayList<CCTV> cctvList;
   public static int[] dx = {-1, 0, 1, 0}; // 상 우 하 좌 시계 방향 순서
   public static int[] dy = {0, 1, 0, -1};
   public static int answer = Integer.MAX_VALUE;

   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      N = sc.nextInt();
      M = sc.nextInt();
      map = new int[N][M];
      cctvList = new ArrayList<>();

      for(int i = 0; i < N; i++) {
         for(int j = 0; j < M; j++) {
            map[i][j] = sc.nextInt();

            if(map[i][j] != 0 &&  map[i][j] != 6) {
               cctvList.add(new CCTV(map[i][j], i, j));
            }
         }
      }
   }
 class CCTV {
   int num;
   int x;
   int y;

   CCTV(int num, int x, int y) {
      this.num = num;
      this.x = x;
      this.y = y;
   }
}

간단하게 먼저 CCTV 위치 INDEX 를 List에 넣어준다.

아래 코드가 사실 가장 중요한 코드 , 경우의 수를 구해주는 코드이다.
output 배열에는 경우의 수가 담겨있다. output.length == CCTV의 개수

public static void permutation(int depth, int r) {
   if(depth == r) {
      // 경우의 수마다 첫 배열을 유지 해야 하기 때문에 새로 만들어준다. 
      copyMap = new int[N][M];
      for(int i = 0; i < map.length; i++) {
         System.arraycopy(map[i], 0, copyMap[i], 0, map[i].length);
      }
		
      // cctv번호와 순열로 뽑혀진 방향에 맞는 상하좌우 방향 설정
      for(int i = 0; i < cctvList.size(); i++) {
         direction(cctvList.get(i), output[i]);
      }

      // 사각 지대 구하기
      // map에서 0인 개수 구하기  
      getBlindSpot();

      return;
   }
   // 여기서 경우의 수의 핵심인 재귀 최대 경우의 수가 4가지 이기 때문에 4번 반복해준다. 
   // 만약 depth가 4고 cctv개수가 4인 경우 CCTV 로직을 시작한다. 
  
	
   for(int i = 0; i < 4; i++) {
      output[depth] = i;
      permutation(depth+1, r);
      // 경우의 수마다 다음과 같이 반복한다. 
      // 0,0,0,0 // 0,0,0,1 // 0,0,0,2
   }
}

CCTV 모니터

public static void direction(CCTV cctv, int d) {
      int cctvNum = cctv.num;

      if(cctvNum == 1) {
         if(d == 0) watch(cctv, 0); // 상
         else if(d == 1) watch(cctv, 1); // 우
         else if(d == 2) watch(cctv, 2); // 하
         else if(d == 3) watch(cctv, 3); // 좌
      } else if(cctvNum == 2) {
               // 2번 CCTV의 경우는 경우의 수가 4가 아닌 2이므로 아래와 같이 2가지 경우의 수로 나누어준다. 

         if(d == 0 || d == 2) {
            watch(cctv, 0); watch(cctv, 2); // 상하
         } else {
            watch(cctv, 1); watch(cctv, 3); // 좌우
         }
      } else if(cctvNum == 3) {
         if(d == 0) {
            watch(cctv, 0); // 상우
            watch(cctv, 1);
         } else if(d == 1) {
            watch(cctv, 1); // 우하
            watch(cctv, 2);
         } else if(d == 2) {
            watch(cctv, 2); // 하좌
            watch(cctv, 3);
         } else if(d == 3) {
            watch(cctv, 0); // 좌상
            watch(cctv, 3);
         }
      } else if(cctvNum == 4) {
         if(d == 0) {
            watch(cctv, 0); // 좌상우
            watch(cctv, 1);
            watch(cctv, 3);
         } else if(d == 1) {
            watch(cctv, 0); // 상우하
            watch(cctv, 1);
            watch(cctv, 2);
         } else if(d == 2) {
            watch(cctv, 1); // 좌하우
            watch(cctv, 2);
            watch(cctv, 3);
         } else if(d == 3) {
            watch(cctv, 0); // 상좌하
            watch(cctv, 2);
            watch(cctv, 3);
         }
      } else if(cctvNum == 5) { // 상우하좌
         watch(cctv, 0);
         watch(cctv, 1);
         watch(cctv, 2);
         watch(cctv, 3);
      }
   }

   // BFS로 방향에 맞게 감시
   public static void watch(CCTV cctv, int d) {
   // 사실 new int[3] 으로 값을 넣어도 되기는 한다. 
   // BFS 가 아니라 그냥 벽또는 map ,  끝까지 가도록 하면 되기는 한다.  
      Queue<CCTV> queue = new LinkedList<>();
      boolean[][] visited = new boolean[N][M];

      queue.add(cctv);
      visited[cctv.x][cctv.y] = true;

      while(!queue.isEmpty()) {
  
         int nx = queue.peek().x + dx[d];
         int ny = queue.poll().y + dy[d];

         // 범위를 벗어나거나 벽을 만나면 끝 -> 한방향 직선이 막히면 당연하게도? 멈춰야겠죠
         if(nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] == 6) {
            break;
         }

         if(copyMap[nx][ny] == 0) {
            copyMap[nx][ny] = -1; // 빈칸이라면 감시할 수 있다는 의미로 -1
            queue.add(new CCTV(cctv.num, nx, ny));
         } else { // 다른 cctv가 있거나 이미 감시된 칸이라면 // CCTV나 감시된 칸 뒤는 통과해서 감시 가능 
            queue.add(new CCTV(cctv.num, nx, ny)); // 그냥 통과
         }
      }
   }

// 각 경우의 수마다 대소비교를 통해 최소값을 구한다. 
public static void getBlindSpot() {
      int cnt = 0;
      for(int i = 0; i < N; i++) {
         for(int j = 0; j < M; j++) {
            if(copyMap[i][j] == 0) {
               cnt++;
            }
         }
      }
      answer = Math.min(answer, cnt);
   }