[BOJ] 15683 감시 - JAVA

1. 문제

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

15683번: 감시

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

CCTV는 CCTV를 통과할 수 있다. 

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

---

2. 풀이

메인함수

• 사무실 정보를 받으면서 cctv는 따로 저장한다. 가로, 세로, cctv종류를 저장했다.

static int N, M, cctvCnt, MIN = Integer.MAX_VALUE;
static char[][] office;
static int[][] cctvs;

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());

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

   office = new char[N][M];
   cctvs = new int[8][3];

   for (int n = 0; n < N; n++) {
      st = new StringTokenizer(in.readLine());
      for (int m = 0; m < M; m++) {
         office[n][m] = st.nextToken().charAt(0);
         if (office[n][m] >= '1' && office[n][m] <= '5') {
            cctvs[cctvCnt][0] = n;
            cctvs[cctvCnt][1] = m;
            cctvs[cctvCnt++][2] = office[n][m] - '0';
         }
      }
   }

   setCCTV(0);

   System.out.println(MIN);

}

 

배열 저장, 사각지대 세는 함수

• 이차원 배열이라 하나하나 값을 넣어줬다. 이 방식 말고도 행 부분만 반복해서 Array.copyOf()나 배열.clone(), System.arraycopy()를 사용해도 된다.

private static int countZero() {
   int cnt = 0;
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
         if (office[i][j] == '0') ++cnt;
      }
   }
   return cnt;
}

private static void copyArray(char[][] origin, char[][] result) {
   for (int i = 0; i < origin.length; i++) {
      for (int j = 0; j < origin[i].length; j++) {
         result[i][j] = origin[i][j];
      }
   }
}

 

CCTV 정보와 시작 방향을 받아서 사무실 상태를 변경하는 함수

CCTV의 시선이 닿는 곳에 '#' 표시를 한다. 이 때, 벽인 '6'을 만나면 그 방향으로는 더 이상 움직이지 않는다. 

CCTV의 종류에 따라 시작 시선방향부터 최대 네 방향까지 감시가 가능하다.

• 1번은 한 방향만 감시 가능하므로 반복하지 않고 바로 break한다.
• 2번은 반대방향만 감시 가능하므로 반복문 끝날때마다 +1을 더해서 최종적으로 i=0일때, i=2일때만 반복하도록 한다.
• 3번은 90도 방향을 감시가능하다. 따라서 i=0,i=1일때 반복을 수행하고 break한다.
• 4번은 시작 방향으로부터 +2방향까지 감시 가능하다. i=2일때까지 반복하고 break한다.
• 5번은 조건문 필요 없이 네 방향 모두 감시하고 끝낸다.

private static void setOffice(int[] cctv, int d) {
   int[][] deltas = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 위, 오른쪽, 아래, 왼쪽 (시계방향)

   for (int i = 0; i < 4; i++) {
      int nn = cctv[0];
      int nm = cctv[1];

      while ((nn+=deltas[(d+i)%4][0]) >= 0 && nn < N 
            && (nm+=deltas[(d+i)%4][1]) >= 0 && nm < M) {

         if (office[nn][nm] == '6') break;
         if (office[nn][nm] == '0') office[nn][nm] = '#';
      }

      if(cctv[2]==1) break;
      else if(cctv[2]==2) ++i;
      else if(cctv[2]==3 && i==1) break;
      else if(cctv[2]==4 && i==2) break;
   }
}

 

CCTV 방향을 정하고 방향마다의 최소값을 찾는 함수

• cnt가 입력받은 총 cctv 개수와 같다면 최소값인지 비교하고 끝낸다.
• 원본을 복사해놓을 배열을 만든다.
• 시작방향은 네가지가 가능하다. 따라서 0번부터 4번 반복한다.
  • 먼저 원본을 tmp에 저장한다.
  • setOffice 함수를 통해 사무실 상태를 변경한다. 
  • 이 상태에서 다음 cctv 경우의 수를 탐색한다.(cnt+1 재귀호출) 
  • 미리 저장해둔 원본으로 다시 되돌린다.

private static void setCCTV(int cnt) {
   if (cnt == cctvCnt) {
      MIN = Math.min(MIN, countZero());
      return;
   }

   char[][] tmpOffice = new char[N][M];

   for (int i = 0; i < 4; i++) {
      copyArray(office, tmpOffice);

      setOffice(cctvs[cnt], i);
      setCCTV(cnt + 1);

      copyArray(tmpOffice, office);
   }

}

---

3. 결과

방향 잘못설정해서 많이 틀렸다. 3번은 90도 방향으로 두 갠데 위아래를 했다거나 그런 실수들.. 

한 줄 한 줄 하드코딩식으로 했는데 그걸 변경해서 코드 길이가 절반이 넘게 줄었다.