[백준] 15683 감시

15683번: 감시

 

www.acmicpc.net

풀이

완전 탐색으로 해결할 수 있는 문제이다. dfs를 통해 모든 CCTV의 방향을 결정해주고 감시할 수 있는 최소값을 구하면 된다.

CCTV가 감시하는 구현해보자.

void observe(int x, int y, int dir) {
    int nx = x; int ny = y;

    while (true) {
        nx += dx[dir]; ny += dy[dir];
        if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1 || tmp[ny][nx] == 6) break;
        if (tmp[ny][nx] != 0) continue;
        tmp[ny][nx] = -1;
    }
}

우선 1번 CCTV와 동일한 방법으로 감시할 수 있도록 함수를 구현하였다.

const int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };

int model = map[y][x];
        observe(x, y, cctv_dir[i]);
        if (model == 2 || model == 4 || model == 5) observe(x, y, (cctv_dir[i] + 2) % 4);
        if (model == 3 || model == 4 || model == 5) observe(x, y, (cctv_dir[i] + 1) % 4);
        if (model == 5) observe(x, y, cctv_dir[i] + 3);

그리고 CCTV 종류별로 규칙을 알아내어 간단하게 구현할 수 있었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, ans;
vector<vector<int>> map, tmp;
vector<pair<int, int>> cctv;
int cctv_dir[8];
const int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };

void observe(int x, int y, int dir) {
    int nx = x; int ny = y;

    while (true) {
        nx += dx[dir]; ny += dy[dir];
        if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1 || tmp[ny][nx] == 6) break;
        if (tmp[ny][nx] != 0) continue;
        tmp[ny][nx] = -1;
    }
}

int simulation() {
    tmp = map;
    int ret = 0;

    for (int i = 0; i < cctv.size(); i++) {
        int x = cctv[i].first; int y = cctv[i].second;
        int model = map[y][x];
        // 1번 cctv처럼 감시
        observe(x, y, cctv_dir[i]);
        // 1번 cctv의 반대방향 감시
        if (model == 2 || model == 4 || model == 5) observe(x, y, (cctv_dir[i] + 2) % 4);
        // 1번 cctv를 기준으로 시계방향으로 90도 회전한 방향 감시
        if (model == 3 || model == 4 || model == 5) observe(x, y, (cctv_dir[i] + 1) % 4);
        // 1번 cctv를 기준으로 반시계방향으로 90도 회전한 방향 감시
        if (model == 5) observe(x, y, cctv_dir[i] + 3);
    }

    // 빈 칸 개수 세기
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!tmp[i][j]) ret++;
    return ret;
}

void dfs(int cnt) {
    if (cnt == cctv.size()) {
        ans = min(ans, simulation());
        return;
    }

    int x = cctv[cnt].first;
    int y = cctv[cnt].second;
    int& tv = map[y][x];

    for (int i = 0; i < 4; i++) {
        // 2번 cctv의 경우 경우가 2가지이므로 0, 1로 표시
        if(tv == 2 && (i == 2 || i == 3)) continue;
        // 5번 cctv는 가능한 경우가 1가지이므로 0으로 표시
        if (tv == 5 && i > 0) continue;
        cctv_dir[cnt] = i;
        dfs(cnt + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    ans = m * n;
    map = vector<vector<int>>(n, vector<int>(m));
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            // cctv 위치 저장
            if (map[i][j] != 0 && map[i][j] != 6)
                cctv.push_back({ j, i });
        }
    dfs(0);
    cout << ans << '\n';
    return 0;
}