[백준] 15683번 감시

15683번 감시

---

1. 이해하기

• CCTV는 5가지 종류가 있다. 종류마다 감시할 수 있는 방법이 다르다.
• CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있지만 벽은 통과해서 감시하지 못한다. 이를 사각지대라 부른다.
• CCTV는 90도 방향으로 회전할 수 있다.
• CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구해야 한다.
• 각 CCTV마다 방향을 달리해 사각지대를 구하는 완전탐색 문제.

---

2. 구현하기

• 카메라의 종류, 현재 위치와 가리키고 있는 방향을 받아와 그 방향으로 감시할 수 있는 영역을 표시한다.

  bool out_of_bound(int x, int y) {
      return x < 0 or x >= N or y < 0 or y >= M;
  }
  
  void mark_view_area(int x, int y, int dir) {
      while(1) {
          if(out_of_bound(x,y) or map[x][y] == 6) break;
          view[x][y] = true;
          x+=dx[dir]; y+=dy[dir];
      }
  }
  
  void camera_work(vector<Camera> camera) {
      int size = camera.size();
      for(int i = 0; i < size; i++) {
          int x = camera[i].x, y = camera[i].y, dir = camera[i].dir;
          if(camera[i].n == 1) {
              int nx = x+dx[dir], ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
          } else if(camera[i].n == 2) {
              int nx = x+dx[dir], ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
              dir = (dir+2)%4; nx = x+dx[dir]; ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
          } else if(camera[i].n == 3) {
              int nx = x+dx[dir], ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
              dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
          } else if(camera[i].n == 4) {
              int nx = x+dx[dir], ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
              dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
              dir = (dir+2)%4; nx = x+dx[dir]; ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
          } else if(camera[i].n == 5) {
              int nx = x+dx[dir], ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
              dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
              dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
              dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
              mark_view_area(nx,ny,dir);
          }
      }
  }

• 각 카메라를 4방향으로 돌려보며 구할 수 있는 사각지대의 최소 영역을 구한다.

  int get_non_view_area() {
      int ret = 0;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < M; j++) {
              if(map[i][j] == 0 and !view[i][j]) ret++;
          }
      }
      return ret;
  }
  
  int solve(vector<Camera> camera, int index) {
      int size = camera.size();
      if(index == size) {
          memset(view,false,sizeof(view));
          camera_work(camera);
          return get_non_view_area();
      }
  
      int ret = MAX;
      for(int i = 0; i < 4; i++) {
          ret = min(ret,solve(camera,index+1));
          int& dir = camera[index].dir;
          dir = (dir+1)%4;
      }
      return ret;
  }

---

3. 전체 코드

• 카메라의 정보를 저장하는 배열을 만들어 따로 저장한다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct Camera{
    int x,y,n,dir;
};
const int MAX = 987654321;
int map[8][8];
bool view[8][8];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int N,M;

int get_non_view_area() {
    int ret = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(map[i][j] == 0 and !view[i][j]) ret++;
        }
    }
    return ret;
}

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

void mark_view_area(int x, int y, int dir) {
    while(1) {
        if(out_of_bound(x,y) or map[x][y] == 6) break;
        view[x][y] = true;
        x+=dx[dir]; y+=dy[dir];
    }
}

void camera_work(vector<Camera> camera) {
    int size = camera.size();
    for(int i = 0; i < size; i++) {
        int x = camera[i].x, y = camera[i].y, dir = camera[i].dir;
        if(camera[i].n == 1) {
            int nx = x+dx[dir], ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
        } else if(camera[i].n == 2) {
            int nx = x+dx[dir], ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
            dir = (dir+2)%4; nx = x+dx[dir]; ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
        } else if(camera[i].n == 3) {
            int nx = x+dx[dir], ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
            dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
        } else if(camera[i].n == 4) {
            int nx = x+dx[dir], ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
            dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
            dir = (dir+2)%4; nx = x+dx[dir]; ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
        } else if(camera[i].n == 5) {
            int nx = x+dx[dir], ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
            dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
            dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
            dir = (dir+1)%4; nx = x+dx[dir]; ny = y+dy[dir];
            mark_view_area(nx,ny,dir);
        }
    }
}

int solve(vector<Camera> camera, int index) {
    int size = camera.size();
    if(index == size) {
        memset(view,false,sizeof(view));
        camera_work(camera);
        return get_non_view_area();
    }

    int ret = MAX;
    for(int i = 0; i < 4; i++) {
        ret = min(ret,solve(camera,index+1));
        int& dir = camera[index].dir;
        dir = (dir+1)%4;
    }
    return ret;
}

int main() {
    vector<Camera> camera;
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> map[i][j];
            if(1 <= map[i][j] and map[i][j] <= 5) {
                camera.push_back({i,j,map[i][j],0});
            }
        }
    }

    cout << solve(camera,0) << '\n';
    return 0;
}