BOJ 15683 : 감시

풀이 요약

조합을 이용한 DFS

풀이 상세

1. 매 카메라의 90도 전환하는 경우의수를 모두 포함하여, 최소 사각지대가 나오는 경우를 찾으면 된다.

2. 하나의 백터안에 카메라의 모든 좌표를 미리 탐색을 통해 저장한다. 카메라를 모두 한번씩 사용해야하므로 $nCn$ 이 되며, 그 안에서 90도씩 전환이 이루어지는 경우이니 실제로는 $4nCn$ 이 되겠다.

3. 나의 경우, 카메라가 2번을 제외한 모든 카메라가 인접함을 이용했다. 예를 들어 시계방향으로 상우하좌를 [0,1,2,3] 이라 한다면 4번 카메라의 모든 경우는 [0,1,2], [1,2,3], [2,3,0], [3,0,1] 이 된다. 이때 맨 마지막 $idx$ 에서 $0$ 으로 이어 질 수 있도록 모듈러 연산을 이용한다.

4. 카메라의 좌표와 탐색할 수 있는 방향이 정해지면 감시를 할 수 있는 만큼 최대한 감시한다. 감시 조건은 범위 인덱스가 N, M 이거나 $0$ 보다 작은 경우 그리고 벽을 만나게 되었을 때이다.

5. 이후 종단점 까지 도달하였다면 사각지대의 갯수를 최소값으로 업데이트한다.

배운점

• 삼성 기출은 늘 징하군.

#include <iostream>
#include <vector>

#define f first
#define s second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
int N, M, ans = 987654321;
vvi v;
vector<pii> list;
vi dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};

void input() {
    cin >> N >> M;
    v = vvi(N, vi(M, 0));
    int num = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> num;
            v[i][j] = num;
            if (v[i][j] <= 5 && v[i][j] >= 1) list.push_back({i, j});
        }
    }
}

vvi copyMap() {
    vvi temp = vvi(N, vi(M, 0));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) temp[i][j] = v[i][j];
    return temp;
}

void copyMapRev(vvi copy) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) v[i][j] = copy[i][j];
}

void go(int r, int c, int d) {
    d %= 4;
    int curr_r = r, curr_c = c;
    while (true) {
        int nr = curr_r + dr[d], nc = curr_c + dc[d];
        curr_r = nr, curr_c = nc;
        if (nr < 0 || nc < 0 || nr >= N || nc >= M || v[nr][nc] == 6) return;
        if (v[nr][nc] > 0) continue;
        v[nr][nc] = -1;
    }
}

int getCount() {
    int temp = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (v[i][j] == 0) temp++;
        }
    }
    return temp;
}

void dfs(int idx) {
    if (idx >= list.size()) {
        ans = min(getCount(), ans);
        return;
    }
    int c = v[list[idx].f][list[idx].s];
    for (int d = 0; d < 4; d++) {
        vvi copy_v = copyMap();
        if (c == 1) go(list[idx].f, list[idx].s, d);
        else if (c == 2) for (int i = 0; i <= 2; i += 2) go(list[idx].f, list[idx].s, d + i);
        else if (c == 3) for (int i = 0; i < 2; i++) go(list[idx].f, list[idx].s, d + i);
        else if (c == 4) for (int i = 0; i < 3; i++) go(list[idx].f, list[idx].s, d + i);
        else if (c == 5) for (int i = 0; i < 4; i++) go(list[idx].f, list[idx].s, d + i);
        dfs(idx + 1);
        copyMapRev(copy_v);
    }
}

void output() {
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie();
    input();
    dfs(0);
    output();
}