[백준] 15683 감시

제한은 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번은 회전에 따라 감시 해제할 필요가 없죠.

또, 각 카메라의 회전 방향만 별도의 배열에 저장하고 넘어간 뒤 모든 카메라의 회전 방향을 지정했을 때(중복 순열의 마지막에) 그 배열을 참조해서 감시 체크를 하고 답을 구하는 식의 코드도 있었습니다.