[백준 15683] 감시

www.acmicpc.net/problem/15683

15683번: 감시

backtracking을 사용한 구현문제이다. 어렵다 흑흑

전체 사무실 크기가 8 * 8 이므로 모든 cctv의 경우의 수를 따져야 한다.

 

구현한 함수는 크게 3가지로

백트래킹 함수 / 씨씨티비로 확인하는 함수 / 사각지대를 카운트하는 함수이다.

 

입력을 받으며 cctv는 위치와 타입에 대해 배열로 따로 저장해두고 모든 cctv에 대해 rotate를 실시해서 가장 작은 사각지대를 도출한다.

 

백트래킹 함수의 로직은

1. 모든 cctv를 확인했다면 사각지대(0의 개수)를 확인하여 최솟값을 찾고 return

2. 아직 확인하지 않은 cctv가 있다면 타입에 맞게 rotate를 진행

이 때 백트래킹이므로 다음 rotate로 넘어가기 전에 배열을 이전 상태로 돌려야한다. memcpy(copyArr, arr)

(2차원 배열 복사는 구현이 어렵지 않으니 직접 함수를 만드는 게 낫다. )

 

watch함수는 방향에 따라 씨씨티비를 확인하는 함수로 한 번에 한 방향만 확인한다. 타입에 따라 양방향을 동시에 확인하는 경우 watch함수를 두번 실행한다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, m, sze;
int arr[8][8];
int answer = 100;

int rotates[6] = {0, 4, 2, 4, 4, 1};

struct CCTV
{
  int type, row, col;
};

CCTV cctvs[8];

int count()
{
  int cnt = 0;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (arr[i][j] == 0)
      {
        cnt++;
      }
    }
  }
  return cnt;
}

void memcpy(int src[8][8], int dst[8][8])
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      dst[i][j] = src[i][j];
    }
  }
}

void watch(int dir, int row, int col)
{

  dir %= 4;
  if (dir == 1) //east
  {
    for (int i = col + 1; i < m; i++)
    {
      if (arr[row][i] == 6)
      {
        break;
      }

      if (arr[row][i] == 0)
      {
        arr[row][i] = -1;
      }
    }
  }
  else if (dir == 3) //west
  {
    for (int i = col - 1; i > -1; i--)
    {
      if (arr[row][i] == 6)
      {
        break;
      }
      if (arr[row][i] == 0)
      {
        arr[row][i] = -1;
      }
    }
  }
  else if (dir == 2) //south
  {
    for (int i = row + 1; i < n; i++)
    {
      if (arr[i][col] == 6)
      {
        break;
      }

      if (arr[i][col] == 0)
      {
        arr[i][col] = -1;
      }
    }
  }
  else if (dir == 0) //north
  {
    for (int i = row - 1; i > -1; i--)
    {
      if (arr[i][col] == 6)
      {
        break;
      }

      if (arr[i][col] == 0)
      {
        arr[i][col] = -1;
      }
    }
  }
}

void BackTracking(int idx)
{
  if (idx == sze)
  {
    int result = count();
    answer = min(result, answer);
    return;
  }

  int type = cctvs[idx].type;
  int row = cctvs[idx].row;
  int col = cctvs[idx].col;
  int copyArr[8][8];

  memcpy(arr, copyArr);

  for (int dir = 0; dir < rotates[type]; dir++)
  {
    if (type == 1)
    {
      watch(dir, row, col);
    }
    else if (type == 2)
    {
      watch(dir, row, col);
      watch(dir + 2, row, col);
    }
    else if (type == 3)
    {
      watch(dir, row, col);
      watch(dir + 1, row, col);
    }
    else if (type == 4)
    {
      watch(dir, row, col);
      watch(dir + 1, row, col);
      watch(dir + 2, row, col);
    }
    else if (type == 5)
    {
      watch(dir, row, col);
      watch(dir + 1, row, col);
      watch(dir + 2, row, col);
      watch(dir + 3, row, col);
    }
    BackTracking(idx + 1);
    memcpy(copyArr, arr);
  }
}

int main(void)
{
  scanf("%d %d", &n, &m);

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      scanf("%d", &arr[i][j]);

      if (arr[i][j] >= 1 && arr[i][j] <= 5)
      {
        cctvs[sze++] = {arr[i][j], i, j};
      }
    }
  }

  BackTracking(0);
  printf("%d\n", answer);
  return 0;
}