C - [회전 설계 실패 백준 15683] 감시

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

 

#include <stdio.h>

#define MAX 8

int n, m;
int map[MAX][MAX];
int cctv_x[MAX], cctv_y[MAX], cctv_type[MAX];
int cctv_count = 0;
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 우, 하, 좌, 상
int result = 64; // 최대값

// 맵을 복사합니다.
void copy_map(int dest[MAX][MAX], int src[MAX][MAX]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dest[i][j] = src[i][j];
        }
    }
}

// 특정 방향으로 감시를 진행합니다.
void watch(int x, int y, int d, int temp_map[MAX][MAX]) {
    while (1) {
        x += directions[d][0];
        y += directions[d][1];
        if (x < 0 || x >= n || y < 0 || y >= m || temp_map[x][y] == 6) break; // 범위를 벗어나거나 벽을 만나면 종료
        if (temp_map[x][y] == 0) temp_map[x][y] = -1; // 감시 영역 표시
    }
}

// 모든 CCTV의 방향 조합을 탐색합니다.
void dfs(int idx, int temp_map[MAX][MAX]) {
    if (idx == cctv_count) { // 모든 CCTV의 방향을 결정했을 때
        int blind_spots = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (temp_map[i][j] == 0) blind_spots++; // 사각지대 카운트
            }
        }
        if (blind_spots < result) result = blind_spots; // 최소값 갱신
        return;
    }

    int x = cctv_x[idx];
    int y = cctv_y[idx];
    int type = cctv_type[idx];
    int backup_map[MAX][MAX];

    for (int d = 0; d < 4; d++) {
        copy_map(backup_map, temp_map);

        if (type == 1) {
            watch(x, y, d, backup_map);
        } else if (type == 2) {
            watch(x, y, d, backup_map);
            watch(x, y, (d + 2) % 4, backup_map); // 반대 방향
        } else if (type == 3) {
            watch(x, y, d, backup_map);
            watch(x, y, (d + 1) % 4, backup_map); // 직각 방향
        } else if (type == 4) {
            watch(x, y, d, backup_map);
            watch(x, y, (d + 1) % 4, backup_map);
            watch(x, y, (d + 2) % 4, backup_map);
        } else if (type == 5) {
            for (int i = 0; i < 4; i++) {
                watch(x, y, i, backup_map); // 모든 방향 감시
            }
        }

        dfs(idx + 1, backup_map); // 다음 CCTV 탐색
    }
}

int main() {
    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 (map[i][j] >= 1 && map[i][j] <= 5) {
                cctv_x[cctv_count] = i;
                cctv_y[cctv_count] = j;
                cctv_type[cctv_count] = map[i][j];
                cctv_count++;
            }
        }
    }

    dfs(0, map);
    printf("%d\n", result);
    return 0;
}