[BOJ/15683/C++] 감시

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

문제

• 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다.
• CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.
• 사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

조건

• 1번 CCTV는 한 쪽 방향만 감시할 수 있다.
• 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다.
• 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.
• 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
• 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
• CCTV의 최대 개수는 8개를 넘지 않는다.

풀이

굉장히 어려웠던 문제였다. 사실 구현도 제대로 못했다. 어떤걸 구현해야 할지는 명확하게 알겠는데, CCTV의 방향들을 어떻게 설정해줘야할지 좋은 아이디어가 떠오르지 않았다.

평소 dx[4],dy[4] 방향벡터에 대한 태도

나는 dx,dy를 단순히 인근좌표를 방문하는 것으로 생각을 했다. 평소대로 for(int dir느낌으로 가려고 하니까, nx,ny값에 어떤 값을 대응해야 할지 규칙성이 보이지 않아 생각의 늪에 빠지게되었다. 예를들어, 4번 카메라 같은 경우 (i,j)라고 할 때,
(i+1,i-1,j+1) , (i+1,i-1,j-1) ,(j-1,j+1,i+1),(j-1,j+1,i-1) 의 경우가 있을텐데,
마지막 3번째 원소가 어떨땐 i에, 어떨땐 j에 대응이 되어서 좌표로 생각하기가 힘들었다.

하지만, 바킹독님의 풀이를 보면서 느낀점 dx,dy를 좌표가 아닌, 방향으로 생각해서 , 북쪽 방향, 동쪽방향으로 생각할 수도 있다는 걸 느꼈다. 이게 왜 크냐면, 카메라의 모든 경우를 좌표적으로 생각하지 않고, 가리키는 방향의 경우의 수가 4가지가 있다 생각하고, 4^n으로 생각할 수 있기 때문이다.

4가지 경우의수 , n가지 경우의수를 숫자로 나타내기

위에서 4^n 경우의 수로 나타낸다는 생각이 정립되었다는 이야기는cctv가 3개가 있다면,
(북쪽,북쪽,북쪽) , (북쪽,북쪽,동쪽) , (북쪽,북쪽,남쪽) .... 과 같이 64가지의 모든 경우의 수를 둘러보겠다는 이야기이다. 여기서 쫌 고난이도 테크닉(?) 팁이 있었다. 바로 진법개념을 응용하는 것이다.

위 같이 (북쪽,북쪽,북쪽 ) => (1,1,1)로 대응이 되고, 001,002,003,010..과 같은 숫자로 바꿀 수 있다. 그리고, 각 자리수가 4^n을 나타내기 때문에 4진법 숫자처럼 생각하면 매우매우 유리하다.

이 생각은 , dx,dy를 가지고 단순히 좌표를 생각했다면 나올 수 없는 풀이이다. 그래서, 각 자릿수자를 추출해서 대응시키면 되겠구나! 라고 생각하고 코드를 짜니까, 그 뒤로는 문제 없이 잘 작성되었다.

2번,5번 같은 경우 사실 2번, 1번으로 반복횟수가 매우 작은 친구들이다.

단순히 5번은 따로 처리를 해줄 수 있을거 같다.

• 얘는 아무리 돌려도 똑같기 때문에 5번이 있다면 board에 자신의 7을 다 표시하고 시작해도 무관할 것 같다.
  2번 같은 경우도 , dir =2,3인 경우에는 continue를 해주는 등의 최적화를 할 수 있습니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define X first
#define Y second
using namespace std;

int N, M;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int ans = 0;

int board1[10][10];
int board2[10][10];
vector<pair<int, int>> cctv_pos;

bool outOfRange(int x, int y)
{
  return (x < 0 || x >= N || y < 0 || y >= M);
}

void init_board()
{
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      board2[i][j] = board1[i][j];
    }
  }
}

void go_cctv(int x, int y, int dir)
{
  dir %= 4;
  while (true)
  {
    x += dx[dir];
    y += dy[dir];
    if (board2[x][y] == 6 || outOfRange(x, y))
      return;
    if (board2[x][y] != 0)
      continue;
    board2[x][y] = 7;
  }
}

void chk_area()
{
  int cnt = 0;
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      if (board2[i][j] == 0)
        cnt++;
    }
  }
  ans = min(ans, cnt);
  return;
}
void solve()
{
  // 모든 경우의 수?
  // 4가지의 방향이 있다고 추상화 -> 4^n가지가 필요함.
  for (int k = 0; k < (1 << 2 * (cctv_pos.size())); k++)
  {
    // 보드 2를 쓰고, 다시 원상복구 시킬 때는 보드 1을 기준으로 해야한다.
    init_board();
    // cctv의 갯수만큼, 방향을 정해줘야한다.
    int tmp = k;
    for (int i = 0; i < cctv_pos.size(); i++)
    {
      int dir = tmp % 4;
      tmp /= 4;

      int cur_x = cctv_pos[i].X;
      int cur_y = cctv_pos[i].Y;

      // 1번 카메라
      if (board1[cur_x][cur_y] == 1)
      {
        go_cctv(cur_x, cur_y, dir);
      }
      else if (board1[cur_x][cur_y] == 2)
      {
        go_cctv(cur_x, cur_y, dir);
        // (0,2) ,(1,3) => (2,4) , (3,5) %4라서 또같음.
        go_cctv(cur_x, cur_y, dir + 2);
      }
      else if (board1[cur_x][cur_y] == 3)
      {
        go_cctv(cur_x, cur_y, dir);
        go_cctv(cur_x, cur_y, dir + 1);
      }
      else if (board1[cur_x][cur_y] == 4)
      {
        go_cctv(cur_x, cur_y, dir);
        go_cctv(cur_x, cur_y, dir + 1);
        go_cctv(cur_x, cur_y, dir + 2);
      }
      else
      {
        go_cctv(cur_x, cur_y, dir);
        go_cctv(cur_x, cur_y, dir + 1);
        go_cctv(cur_x, cur_y, dir + 2);
        go_cctv(cur_x, cur_y, dir + 3);
      }
    }
    // 사각영역 체크
    chk_area();
  }
  cout << ans << '\n';
  return;
}

int main()
{
  fastio;
  cin >> N >> M;
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      cin >> board1[i][j];
      if (board1[i][j] != 0 && board1[i][j] != 6)
        cctv_pos.push_back({i, j});
      if (board1[i][j] == 0)
        ans++;
    }
  }
  solve();
  return 0;
}

참고: 바킹독님의 알고리즘