제한은 1초 512MB
맵의 크기는 8*8, 카메라를 4방향으로 돌릴 수 있고 카메라의 최대 갯수는 8개입니다.
카메라 8대 각각의 방향을 한 번씩 바꿔볼 때 나올 수 있는 경우의 수는 4^8 = 2^16 = 64k 번입니다. 카메라 각각은 고유함으로 중복은 없습니다. 각 경우에 사각 지역을 찾는 것은 8*8로 대충 100입니다. 64k * 100 = 6.4m 번입니다. 대충 1g 번 명령을 수행할 때 1초가 걸린다고 계산하면 6.4m 번은 0.01초(10ms) 이내에 수행될 수 있다고 생각합니다. 물론 카메라의 감시 영역을 체크하면서 수행될 명령문은 생각하지 않았지만 이를 차치하고서라도 시간은 충분해보입니다.
중복 순열은 재귀문으로 간단하게 작성할 수 있습니다.
void 중복순열(int 카메라 번호) { /* 최대 카메라 갯수 = 8 */
if 모든 카메라의 방향을 조정 ?
맵의 사각 지역을 카운트
return;
for (감시 방향) /* 방향 = 4 */
감시 체크
중복순열(이번 카메라 번호 + 1) // 다음 카메라로 넘어감
감시 해제
}
다음은 감시 체크와 해제를 하는 부분입니다. 우선 한 지점으로부터 한 방향으로 인자에 따라 감시 체크나 해제를 하는 함수를 만들었습니다. 감시 체크시에는 맵에서 -1을 하고 해제시엔 +1을 했습니다. 음의 정수의 크기로 중복 감시되는 지역을 표현했습니다.
int check(int x, int y) {
if (x < 0 || N <= x || y < 0 || M <= y || map[x][y] == 6) return -1;
if (0 < map[x][y] && map[x][y] < 6) return 0;
return 1;
}
void observe(int x, int y, int d, bool f) { // x,y 지점으로부터 d 방향으로 f (감시or해제)합니다.
int xx = x + dir[d][0];
int yy = y + dir[d][1];
int c = check(xx, yy);
while (c >= 0) {
if (c) {
map[xx][yy] += f ? -1 : 1;
}
xx += dir[d][0];
yy += dir[d][1];
c = check(xx, yy);
}
}
카메라 특성에 맞게 observe() 함수를 호출할 수 있도록 각 카메라에 대한 정보를 배열에 담아 참조하도록 했습니다.
int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
int spec[5/*cctv*/][5/*time*/][4/*direction*/] = {
{ {1, 4}, {0}, {1}, {2}, {3} },
{ {2, 2}, {0, 1}, {2, 3}, {}, {} },
{ {2, 4}, {0, 3}, {0, 2}, {1, 2}, {1, 3} },
{ {3, 4}, {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3} },
{ {4, 1}, {0, 1, 2, 3}, {}, {}, {}}
};
3차원 배열이며 첫 번째는 카메라의 번호를 뜻합니다. 1번 카메라에 대한 정보는 spec[0] 번에 저장됩니다. 두 번째는 카메라 회전 횟수를 의미합니다. 동서남북 방향으로 4회가 최대입니다. 하지만, 특정 카메라의 경우엔 네 방향 모두 돌릴 필요가 없습니다. 예를 들어, 2번 카메라의 경우엔 가로, 세로 2번만 회전시키면 됩니다. 카메라마다 필요한 감시 횟수가 다름으로 이를 두 번째의 0번째 공간을 활용해 표현했습니다. 예를 들어 spec[0][0], {1, 4} 는 1번 카메라가 한 번에 1방향만 탐색하고 4회 회전해야함을 의미합니다. 마지막은 확인해야할 방향을 의미합니다. dir[][] 배열을 이용해서 0~3의 정수로 동서남북을 표현하였습니다.
전체 코드입니다.
#pragma warning(disable: 4996)
#include <stdio.h>
int N, M, map[10][10], ans = 0x7fffffff;
int cctv[10][2], K;
int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
int spec[5/*cctv*/][5/*time*/][4/*direction*/] = {
{ {1, 4}, {0}, {1}, {2}, {3} },
{ {2, 2}, {0, 1}, {2, 3}, {}, {} },
{ {2, 4}, {0, 3}, {0, 2}, {1, 2}, {1, 3} },
{ {3, 4}, {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3} },
{ {4, 1}, {0, 1, 2, 3}, {}, {}, {}}
};
int check(int x, int y) {
if (x < 0 || N <= x || y < 0 || M <= y || map[x][y] == 6) return -1;
if (0 < map[x][y] && map[x][y] < 6) return 0;
return 1;
}
void observe(int x, int y, int d, bool f) {
int xx = x + dir[d][0];
int yy = y + dir[d][1];
int c = check(xx, yy);
while (c >= 0) {
if (c) {
map[xx][yy] += f ? -1 : 1;
}
xx += dir[d][0];
yy += dir[d][1];
c = check(xx, yy);
}
}
void solve(int cctvn) {
if (cctvn >= K) {
int area = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
area += (map[i][j] == 0);
if (area < ans)
ans = area;
return;
}
const int& x = cctv[cctvn][0];
const int& y = cctv[cctvn][1];
const int& cctvkind = map[x][y];
const int& filltime = spec[cctvkind - 1][0][1];
const int& fillcount = spec[cctvkind - 1][0][0];
for (int i = 0; i < filltime; i++) {
for (int j = 0; j < fillcount; j++)
observe(x, y, spec[cctvkind - 1][i + 1][j], true);
solve(cctvn + 1);
for (int j = 0; j < fillcount; j++)
observe(x, y, spec[cctvkind - 1][i + 1][j], false);
}
}
int main(void) {
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
scanf("%d", &map[i][j]);
if (0 < map[i][j] && map[i][j] < 6)
cctv[K][0] = i, cctv[K++][1] = j;
}
solve(0);
printf("%d\n", ans);
return 0;
}
다른 분들의 코드에선 5번 카메라는 회전에 관계없이 고정이므로 아예 처음에 감시 체크를 하고 중복 순열에서 제외시키는 모습을 볼 수 있었습니다. 확실히 5번은 회전에 따라 감시 해제할 필요가 없죠.
또, 각 카메라의 회전 방향만 별도의 배열에 저장하고 넘어간 뒤 모든 카메라의 회전 방향을 지정했을 때(중복 순열의 마지막에) 그 배열을 참조해서 감시 체크를 하고 답을 구하는 식의 코드도 있었습니다.
