백준 15683번 : 감시 (자바)

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

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번	2번	3번	4번	5번

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

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

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

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

→	←	↑	↓

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

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

---

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.

---

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

🔵풀이

구현해야할 조건이 많은 문제입니다. 기본적인 알고리즘은 dfs를 필요로 합니다. 구현 방식의 큰틀을 정해놓고 하나하나 구현하다 보니 풀수  있었습니다. 저는 Cctv 클래스를 만들고 그 안에 정적 팩토리 메소드를 통해 Cctv의 종류에 따라 객체를 반환할 수 있도록 하였습니다. 그리고 모든 경우의 수를 파악하기 위해 dfs를 통하여 각 cctv마다 가능한 모든 방향을 조사하여 최솟값을 구하였습니다. 조사할 때마다  깊은 복사를 통해 copymap을 전달해주었습니다. 그리고 방향은 기존 cctv의 방향에서 %4를 해주어 시계방향으로 돌아갈 수 있도록 하였습니다.

 

코드는 다음과 같습니다.

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

class Main {
  static int N;
  static int M;
  static int[] dx = {0, -1, 0, 1};
  static int[] dy = {-1, 0, 1, 0};
  static ArrayList<int[]> cctv = new ArrayList<>();
  static int anwser = Integer.MAX_VALUE;
  static int[][] original;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.valueOf(st.nextToken());
    M = Integer.valueOf(st.nextToken());
    original = new int[N][M];

    for (int i=0; i<N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        original[i][j] = Integer.valueOf(st.nextToken());
        if (original[i][j]!=0&&original[i][j]!=6){
          cctv.add(new int[]{i,j});
        }
      }
    }

    dfs(original,0);

    System.out.println(anwser);

  }
  static void dfs(int[][] map, int count){
    if (count== cctv.size()){
      anwser = Math.min(anwser,fourRegion(map));
      return;
    }
    int[][] copy = new int[map.length][map[0].length];


    int y = cctv.get(count)[0];
    int x = cctv.get(count)[1];

    int num = map[y][x];
    Cctv cctv1 = Cctv.of(num);

    for (int i=0; i<4; i++) {
      for (int j=0; j<map.length; j++){
        copy[j] = map[j].clone();
      }

      for (int j = 0; j < cctv1.direction.length; j++) {
        int ny = y;
        int nx = x;
        while (ny >= 0 && nx >= 0 && ny <= N - 1 && nx <= M - 1 && map[ny][nx] != 6) {
          if (map[ny][nx] == 0) {
            copy[ny][nx] = 7;
          }
          ny += dy[(cctv1.direction[j]+i)%4];
          nx += dx[(cctv1.direction[j]+i)%4];
        }
      }
      dfs(copy, count + 1);
    }
  }
  static int fourRegion(int[][] map){
    int count = 0;

    for (int i=0; i< map.length; i++){
      for (int j=0; j<map[i].length; j++){
        if (map[i][j]==0){
          count++;
        }
      }
    }
    return count;
  }
  static class Cctv{
   int[] direction;

   static Cctv of(int number){
     Cctv cctv = new Cctv();
     switch (number){
       case 1:
         cctv.direction = new int[1];
         cctv.direction[0] = 3;
         break;
       case 2:
         cctv.direction = new int[2];
         cctv.direction[0] = 3;
         cctv.direction[1] = 1;
         break;
       case 3:
         cctv.direction = new int[2];
         cctv.direction[0] = 3;
         cctv.direction[1] = 2;
         break;
       case 4:
         cctv.direction = new int[3];
         cctv.direction[0] = 3;
         cctv.direction[1] = 2;
         cctv.direction[2] = 1;
         break;
       case 5:
         cctv.direction = new int[4];
         cctv.direction[0] = 3;
         cctv.direction[1] = 2;
         cctv.direction[2] = 1;
         cctv.direction[3] = 0;
         break;
     }
     return cctv;
   }
  }
}

 

시간도 양호한것 같다