문제 링크
문제 해석
문제를 간단하게 해석해 보자.
N x M 크기의 보드가 주어지고, 해당 보드에는 CCTV, 벽이 설치되어 있다.
CCTV는 그 종류에 따라서 감시할 수 있는 방향이 정해져있다.
각 CCTV는 중간에 벽을 만나지 않는 이상 자신이 감시하는 방향에 있는 모든 칸들을 감시할 수 있다.(CCTV를 중간에 만나도 그 뒤쪽 칸을 감시할 수 있다.)
그리고 우리가 구해야 하는 답은 이 CCTV들을 적절히 회전시켜서 감시되지 않는 사각지대 칸을 최소로 만들고, 그때의 사각지대 칸의 수를 구하는 것이다.
풀이 과정
이런 문제에서 가장 먼저 떠오르는 해법은 역시 모든 경우의 수를 테스트 해 보는 브루트포스 방식이다.
CCTV의 위치는 입력에서 주어지고 바꿀 수 없기 때문에, CCTV를 회전시켜 만들 수 있는 모든 경우의 수를 테스트 해 보면 될 것이다.
브루트포스 방식의 코드를 구현하기 전, 시간제한 조건에 걸리지 않는지 확인해 보아야 한다.
주어지는 보드의 크기는 8 x 8 이하이고, 주어지는 CCTV의 수는 8개 이하이다.
각 CCTV는 90도씩 회전시킬 수 있으므로 총 4회까지 회전시킬 수 있다.
즉, 8개의 CCTV를 회전시키는 모든 경우의 수는
= 65536
66536개이고, 각 경우의 수에 대해서 사각지대의 수를 셀 때는 보드를 모두 탐색해 보아야 하므로
8x8 = 64
즉, 답을 구하는데 필요한 총 연산의 수는 최대 65536 x 64 = 4194304 회이다.
단위가 백만 단위이니, 1초라는 시간 제한에 충분히 맞출 수 있는 상황이라고 할 수 있겠다.
구현
구현해야 할 항목은 크게 2가지이다.
1. 각 CCTV를 회전시키는 모든 경우의 수를 탐색하는 로직
2. 각 CCTV 배치 상태에서 사각지대의 수를 세는 로직
1번 항목은 DFS를 통해서 구현하였다.
int DFS(int camIndex)
{
if (camIndex == camInfo.size())
return check();
if (camInfo[camIndex].type == 5)
return DFS(camIndex + 1);
int ret = 999999;
for (int i = 0; i < 4; i++)
{
camInfo[camIndex].rot = i;
ret = min(ret, DFS(camIndex + 1));
}
return ret;
}DFS를 통해 각 CCTV의 회전 횟수를 0 ~ 3까지 세팅하고, 모든 카메라의 회전 횟수를 세팅하면 check() 함수를 통해서 사각지대의 수를 센다.
만약 CCTV 타입이 5인 경우(4방향 모두 감시 가능한 CCTV), 성능 개선을 위해 회전을 따로 시키지 않고 바로 다음 CCTV의 회전 횟수를 세팅한다.
2번 항목은 사실 빡구현이라 전체 코드랑 같이 보는게 도움이 될 것 같다.
전체 코드
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int dy[4] = { 0, -1, 0, 1 };
int dx[4] = { -1, 0, 1, 0 };
typedef struct CCTV {
int r, c;
int type;
int rot;
}CCTV;
vector<vector<int>> camera = {
{2},
{0, 2},
{1, 2},
{0, 1, 2},
{0, 1, 2, 3}
};
int arr[8][8];
vector<CCTV> camInfo;
int N, M;
int check()
{
int copyArr[8][8];
memcpy(copyArr, arr, sizeof(arr));
for (CCTV cctv : camInfo)
{
for (int dir : camera[cctv.type])
{
dir = (dir + cctv.rot) % 4;
int step = 1;
while (1)
{
int nr = cctv.r + dy[dir] * step;
int nc = cctv.c + dx[dir] * step;
if (nr < 0 || nr >= N || nc < 0 || nc >= M) break;
if (copyArr[nr][nc] == 6) break;
copyArr[nr][nc] = 9;
step++;
}
}
}
int ret = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (copyArr[i][j] == 0)
ret++;
}
}
return ret;
}
int DFS(int camIndex)
{
if (camIndex == camInfo.size())
return check();
if (camInfo[camIndex].type == 5)
return DFS(camIndex + 1);
int ret = 999999;
for (int i = 0; i < 4; i++)
{
camInfo[camIndex].rot = i;
ret = min(ret, DFS(camIndex + 1));
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> arr[i][j];
if (arr[i][j] != 0 && arr[i][j] != 6)
{
camInfo.push_back({ i, j, arr[i][j] - 1, 0 });
continue;
}
}
}
cout << DFS(0);
return 0;
}2번 항목의 경우 check() 함수에 구현하였는데, 코드가 길긴 하지만 하는 일은 단순하다.
1. 우선 입력받은 보드를 복사해온다.
2. 그리고 CCTV가 감시할 수 있는 칸들을 복사해 온 보드에 마킹한다.
3. 마지막으로 복사해 온 보드를 쭉 스캔하며 마킹되지 않은 칸의 수를 센다.
