[JAVA] BOJ 백준 15683 감시

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

15683번: 감시

문제

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

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

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

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

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개를 넘지 않는다.

출력

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

코드

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_15683 {
    static int N;
    static int M;
    static int max;
    static int num;
    static int[][] office;
    static int[][] cctv;
    static int[][] dir;
    static int result;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        if (N > M)
            max = N;
        else
            max = M;
        office = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine(), " ");
            for (int j = 0; j < M; j++) {
                office[i][j] = Integer.parseInt(st.nextToken());
                if (office[i][j] != 0 && office[i][j] != 6)
                    num++;
            }
        }
        cctv = new int[num][3];
        dir = new int[][] { { 0, 0, 0, 1 }, { 0, 1, 0, 1 }, { 1, 0, 0, 1 }, { 1, 1, 0, 1 }, { 1, 1, 1, 1 } };
        int k = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (office[i][j] != 0 && office[i][j] != 6) {
                    cctv[k][0] = i;
                    cctv[k][1] = j;
                    k++;
                }
        result = N * M;
        dfs(0);
        sb.append(result).append("\\n");
        System.out.println(sb.toString());
    }

    static void dfs(int count) {
        if (count == num) {
            count();
            return;
        }
        if (office[cctv[count][0]][cctv[count][1]] == 2)
            for (int i = 0; i < 2; i++) {
                cctv[count][2] = i;
                dfs(count + 1);
            }
        else if (office[cctv[count][0]][cctv[count][1]] == 5) {
            cctv[count][2] = 1;
            dfs(count + 1);
        } else {
            for (int i = 0; i < 4; i++) {
                cctv[count][2] = i;
                dfs(count + 1);
            }
        }
    }

    static void count() {
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        int status = 0;
        int count = 0;
        int[][] check = new int[N][M];
        for (int u = 0; u < N; u++)
            System.arraycopy(office[u], 0, check[u], 0, M);
        int nx, ny;
        for (int i = 0; i < num; i++) {
            status = office[cctv[i][0]][cctv[i][1]];
            for (int d = 0; d < 4; d++) {
                if (dir[status - 1][d] == 0)
                    continue;
                end: for (int k = 1; k < max; k++) {
                    nx = cctv[i][0] + k * dx[(d + cctv[i][2]) % 4];
                    ny = cctv[i][1] + k * dy[(d + cctv[i][2]) % 4];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M || office[nx][ny] == 6)
                        break end;
                    else
                        check[nx][ny] = 9;
                }
            }
        }

        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (check[i][j] == 0)
                    count++;
        if (count < result)
            result = count;
    }
}

한줄씩 살펴보자!

static int N;
static int M;
static int max;
static int num;
static int[][] office;
static int[][] cctv;
static int[][] dir;
static int result;

전역 변수로 사용할 변수는 다음과 같다.

max는 N, M 중 더 큰 값을 담고 있다. cctv는 벽이 닿거나 칸을 벗어날 때까지 조사할 수 있기 때문에 조사할 수 있는 최대 길이는 max-1이 된다.

num의 cctv의 개수 정보를 담고 있다.

office 배열은 사무실의 정보를 담고 있다.

cctv 배열은 각 cctv의 위치, 방향을 담고 있다.

dir 배열은 1~5 번 cctv가 조사할 수 있는 방향의 정보를 0, 1로 표현한다. 밑에서 다시 설명하겠다.

for (int i = 0; i < N; i++) {
      st = new StringTokenizer(bf.readLine(), " ");
      for (int j = 0; j < M; j++) {
          office[i][j] = Integer.parseInt(st.nextToken());
          if (office[i][j] != 0 && office[i][j] != 6)
              num++;
      }
  }

office 정보를 입력 받음과 동시에 cctv의 개수를 num 변수에 담아준다.

cctv = new int[num][3];
dir = new int[][] { { 0, 0, 0, 1 }, { 0, 1, 0, 1 }, { 1, 0, 0, 1 }, { 1, 1, 0, 1 }, { 1, 1, 1, 1 } };
int k = 0;
for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
        if (office[i][j] != 0 && office[i][j] != 6) {
            cctv[k][0] = i;
            cctv[k][1] = j;
            k++;
        }
result = N * M;

dir 배열을 보았을 때 dir[0]에는 cctv 1번이 조사할 수 있는 방향에 대한 조사가 나와있다. cctv는 한쪽 방향 밖에 보지 못하므로 3번 인덱스에만 1의 값을 주었다.

나는 북, 서, 남, 동 순으로 그림을 참고하여 0, 1로 표현하였다. 백준 그림에 따르면 1번 cctv는 동쪽만을 바라보고 있으므로 3번을 1로 설정하였다.

for문을 통해 cctv의 행렬 정보를 배열에 담아준다. 이때 cctv의 위치 값이 있으므로 몇번 cctv인지에 대한 정보를 따로 담아두지는 않았다.

result는 결과값을 담을 변수로 최소값을 구하기 때문에 문제에서 나올수 있는 가능한 최대값인 N*M으로 초기화 하였다.

static void dfs(int count) {
    if (count == num) {
        count();
        return;
    }

dfs 함수를 통해 모든 cctv의 방향 설정을 해줄 것이다.

count는 여태 설정된 cctv의 개수를 뜻한다. num과 같아지면 모든 cctv의 설정이 끝났기 때문에 count함수를 통해 사각지대를 계산하고 return하여 함수를 종료한다.

if (office[cctv[count][0]][cctv[count][1]] == 2)
    for (int i = 0; i < 2; i++) {
        cctv[count][2] = i;
        dfs(count + 1);
    }
else if (office[cctv[count][0]][cctv[count][1]] == 5) {
    cctv[count][2] = 1;
    dfs(count + 1);
} else {
    for (int i = 0; i < 4; i++) {
        cctv[count][2] = i;
        dfs(count + 1);
    }
}

2번 cctv와 5번 cctv는 다른 것과는 달리 4방향 회전 중 같아지는 것이 존재하여 함수의 속도를 증가시키기 위하여 분리하였다.

count번째 cctv의 방향을 설정해주고 dfs함수를 실행한다.

static void count() {
  int[] dx = { -1, 0, 1, 0 };
  int[] dy = { 0, -1, 0, 1 };
  int status = 0;
  int count = 0;
  int[][] check = new int[N][M];
  for (int u = 0; u < N; u++)
      System.arraycopy(office[u], 0, check[u], 0, M);

dx, dy는 북, 서, 남, 동 순으로 방향을 설정해주는 배열이다.

status는 조사할 cctv의 번호를 저장하는 변수이다.

count변수를 통해 사각지대를 저장한다.

check 배열을 통해 office 배열을 깊은 복사 해준다. office 배열은 모든 상황을 조사할 때 쓰이기 때문에 수정을 하면 원래 상태로 바꾸어주어야 한다. 그러므로 check라는 새로운 배열을 통해 수정을 할 것이다.

int nx, ny;
for (int i = 0; i < num; i++) {
    status = office[cctv[i][0]][cctv[i][1]];

nx, ny를 통해 cctv가 감시할 구역의 위치 정보를 저장할 것이다.

첫번째 for loop는 cctv의 개수이다. 저장된 cctv 정보를 토대로 모든 cctv의 감시구역을 확인한다.

status에 cctv의 번호를 저장해준다.

for (int d = 0; d < 4; d++) {
      if (dir[status - 1][d] == 0)
          continue;

두번째 for loop를 통해 북, 서, 남, 동의 네 방향을 조사할 것이다. 이때 dir배열을 통해 cctv의 해당 번호가 조사할 방향이 아닌 경우 continue를 시행한다.

end: for (int k = 1; k < max; k++) {
      nx = cctv[i][0] + k * dx[(d + cctv[i][2]) % 4];
      ny = cctv[i][1] + k * dy[(d + cctv[i][2]) % 4];
      if (nx < 0 || ny < 0 || nx >= N || ny >= M || office[nx][ny] == 6)
          break end;
      else
          check[nx][ny] = 9;
  }

해당 방향 쪽의 모든 구역을 조사해야 하기 때문에 k를 max까지로 설정해준다.

이때 원래는 k * dx[d]로 표현해야 하지만 cctv의 회전을 고려하여 회전 정보가 담긴 cctv[i][2]를 더 해준다. index가 3을 넘지 않아야 하므로 합을 4로 나눈 몫을 인덱스 정보에 넣어준다.

만약 격자를 벗어나거나 벽인 경우 그 방향은 더 이상 조사하지 않는다.

아닌 경우 cctv의 감시 구역이므로 9로 표시한다.

for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
        if (check[i][j] == 0)
            count++;

if (count < result)
    result = count;

이중 loop를 통해 0인 구역(사각지대)의 개수를 조사한다. 가능한 count 중 최소값을 찾아 result에 넣어준다.