[BOJ] 15683. 감시(구현, 시뮬레이션).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

각 CCTV가 감시할 수 있는 방법이 모두 다른데

90도로 회전까지 가능하다.

각 CCTV가 회전하면서 감시할 수 있는 방법을 어떻게 처리하는지가

포인트일 것 같다.

모든 CCTV를 90도씩 회전시키는 방법도 있겠지만,

나는 각 CCTV가 회전하면서 감시할 수 있는 영역을 미리 구해주었다.

    static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1}; // 방향
    static int[][][] ccDir = { // 각 cctv가 볼 수 있는 영역(회전)
            {{0}},
            {{1}, {2}, {3}, {0}}, // 1번 cctv
            {{1, 3}, {0, 2}}, // 2번 cctv
            {{0, 1}, {1, 2}, {2, 3}, {3, 0}}, // 3번 cctv
            {{0, 1, 3}, {0, 1, 2}, {1, 2, 3}, {2, 3, 0}}, // 4번 cctv
            {{0, 1, 2, 3}}, // 5번 cctv
    };

오래 걸리는 노가다도 아니고,

미리 해(?)를 구해놓음으로써 실행 속도도 더 향상시킬 수 있을 것 같았다.

이제 구현단계만 남았다 !!

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ15683 {       static int N, M, res, ccCnt;     static CCTV[] cctvs;     static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1}; // 방향     static int[][][] ccDir = { // 각 cctv가 볼 수 있는 영역(회전)             {{0}},             {{1}, {2}, {3}, {0}}, // 1번 cctv             {{1, 3}, {0, 2}}, // 2번 cctv             {{0, 1}, {1, 2}, {2, 3}, {3, 0}}, // 3번 cctv             {{0, 1, 3}, {0, 1, 2}, {1, 2, 3}, {2, 3, 0}}, // 4번 cctv             {{0, 1, 2, 3}}, // 5번 cctv     };          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()); // 가로         int[][] map = new int[N][M];         cctvs = new CCTV[8];                  int remain = 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());                 // CCTV일 경우                 if(map[i][j] >= 1 && map[i][j] <= 5) {                     cctvs[ccCnt++] = new CCTV(map[i][j], i, j);                                 }                  // 벽일경우                 else if(map[i][j] == 6) remain--;             }         }                  res = Integer.MAX_VALUE;                  process(0, remain - ccCnt, map);                  System.out.println(res);     }       private static void process(int idx, int remain, int[][] map) {                  // 모든 CCTV의 감시 영역을 확인했다면         if(idx == ccCnt) {             // 사각 지대의 최소 크기 갱신             res = Math.min(res, remain);               return;         }                  int[][] newMap = new int[N][M];         copy(newMap, map);                  // 각 CCTV를 확인         CCTV cc = cctvs[idx];                  // 해당 CCTV가 90도씩 회전하며 감시         for (int j = 0; j < ccDir[cc.type].length; j++) {             // 해당 CCTV가 감시할 수 있는 방향으로 감시             int check = 0;             // 현재 상태에서 감시할 수 있는 방향             for (int k = 0; k < ccDir[cc.type][j].length; k++) {                 int d = ccDir[cc.type][j][k];                 check += observation(cc.r, cc.c, d, newMap);             }                          process(idx + 1, remain - check, newMap);             // 다른 방향으로도 확인해보기 위해 map 상태를 되돌리자.             copy(newMap, map);         }              }          private static int observation(int r, int c, int d, int[][] map) {                  // 감시할 수 있는 영역의 수         int cnt = 0;                  while(true) {                          r += dr[d];             c += dc[d];                          // 범위를 벗어나거나 벽이 있다면             if(r < 0 || r >= N || c < 0 || c >= M || map[r][c] == 6) return cnt;             // 다른 CCTV가 있거나 이미 감시된 영역일 경우 pass             if((map[r][c] >= 1 && map[r][c] <= 5) || map[r][c] == -1) continue;             // 빈 칸일 경우             map[r][c] = -1;             cnt++;         }              }       private static void copy(int[][] newMap, int[][] map) {                  for (int i = 0; i < N; i++) {             for (int j = 0; j < M; j++) {                 newMap[i][j] = map[i][j];             }         }              }       static class CCTV {         int type, r, c;           public CCTV(int type, int r, int c) {             this.type = type;             this.r = r;             this.c = c;         }              }   }   Colored by Color Scripter

cs

line 46) 초기 remain은 결국 (전체 영역) - (벽의 개수) - (CCTV 개수)

line 68) 결국 ccDir[cc.type].length 는 해당 CCTV가 회전할 수 있는 방법의 수

line 72) ccDir[cc.type][j].length 는 해당 CCTV가 j번째 회전 방법으로 감시할 수 있는 방향의 수

line 79) 다른 방향으로도 감시해보기 위해 map 상태를 되돌리는 작업이다.

  이 작업을 대신할 수 있는 다른 방법을 사용하면 시간을 더 빠르게 할 수 있을 것 같은데..

  더 생각이 필요하드다..