[DFS] BJ15683 감시

문제 출처: https://www.acmicpc.net/problem/15683

 

Solution

• DFS 탐색으로 각 감시 카메라의 방향을 완전 탐색하고, 각 카메라의 속성에 따라 감시 지역을 구하여 사각 지대를 구하며 최소 값을 갱신한다.

Point

• DFS 완전 탐색은 어렵지 않았으나 각 카메라의 방향이 정해진 뒤 감시 구역을 구하는 것이 까다로웠다.
• BFS와 비슷한 로직으로 전진 방향에 대한 감시 구역을 구하도록 했다.
• vision() 함수에서 카메라 속성에 따라 여러 방향으로 search() 함수를 각각 수행하도록 했는데, search() 함수에서 한번에 처리하게 하면 더 빠르게 동작할 것 같다.

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

struct cctv {
    int r, c, k, dir;
};

int N, M;
int map[8][8];
int new_map[8][8];
vector<cctv> cc;
int dr[] = { -1, 0, 1, 0 }; // N E S W
int dc[] = { 0, 1, 0, -1 };
int ans;

void input() {
    ans = 987654321;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (0 < map[i][j] && map[i][j] < 6) cc.push_back({ i, j, map[i][j], 0 });
        }
    }
}

int blindArea() {
    int result = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (new_map[i][j] == 0) result++;
    return result;
}

void search(int r, int c, int dir) {
    queue<pair<int, int>> q;
    q.push({ r, c });
    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        int nr = cur.first + dr[dir], nc = cur.second + dc[dir];
        if (nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc]==6) break;
        else {
            new_map[nr][nc] = -1;
            q.push({ nr, nc });
        }
    }
}

void vision() {
    for (int i = 0; i < cc.size(); i++) {
        if (cc[i].k == 1) search(cc[i].r, cc[i].c, cc[i].dir);
        else if (cc[i].k == 2) {
            search(cc[i].r, cc[i].c, cc[i].dir);
            search(cc[i].r, cc[i].c, (cc[i].dir + 2) % 4);
        }
        else if (cc[i].k == 3) {
            search(cc[i].r, cc[i].c, cc[i].dir);
            search(cc[i].r, cc[i].c, (cc[i].dir + 1) % 4);
        }
        else if (cc[i].k == 4) {
            search(cc[i].r, cc[i].c, cc[i].dir);
            search(cc[i].r, cc[i].c, (cc[i].dir + 1) % 4);
            search(cc[i].r, cc[i].c, (cc[i].dir + 2) % 4);
        }
        else {
            search(cc[i].r, cc[i].c, cc[i].dir);
            search(cc[i].r, cc[i].c, (cc[i].dir + 1) % 4);
            search(cc[i].r, cc[i].c, (cc[i].dir + 2) % 4);
            search(cc[i].r, cc[i].c, (cc[i].dir + 3) % 4);
        }
    }
}

void dfs(int d) {
    if (d == cc.size()) {
        memcpy(new_map, map, sizeof(new_map));
        vision();
        ans = min(ans, blindArea());
        return;
    }
    for (int i = 0; i < 4; i++) { //dir
        cctv cur = cc[d];
        cc[d].dir = i;
        dfs(d + 1);
        cc[d].dir = cur.dir;
    }
}

int main() {
    input();
    dfs(0);
    cout << ans << endl;
}