15683번-감시

문제

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

15683번: 감시

---

접근방법

1) 접근 사고

1.CCTV의 갯수만큼 DFS를 진행해야 합니다. 각 재귀함수마다 회전할 수 있는 방향의 경우의 수를 계산해야 하기 때문입니다.

2.DFS를 진행한 뒤에는 방향을 회전시킵니다.

3.1 ~ 2를 반복한 뒤에 탐색이 CCTV의 모든 경우를 탐색했다면 안전 구역의 값을 최소값으로 최신화 합니다.

 

2) 시간 복잡도

완전 탐색이므로 O(N^2)을 가집니다.

 

3) 배운 점

방향에 대한 전환이 각 경우마다 다르기 때문에 구현할 때 실수를 했습니다. 덕분에 디버깅 실력이 늘었네요

 

4) PS

구현 문제는 기능별로 분할하는것이 디버깅할 때 훨씬 편합니다.

---

정답 코드

#include<bits/stdc++.h>
 
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X, Y) make_pair(X,Y)
#define mt(X, Y) make_tuple(X,Y)
#define mtt(X, Y, Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
/*
4 6
0 0 0 0 0 0
0 0 6 0 0 0
0 6 3 6 0 0
0 0 6 0 0 0
 */
using namespace std;
const int MAX = 9;
int n, m;
int board[MAX][MAX];
int ret = INT_MAX;
 
vector<pair<int, int>> cctv;
 
int main(void) {
    cout << (1 << 6) <<"\n";
    fastio;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            if (board[i][j] >= 1 && board[i][j] <= 5)
                cctv.push_back({i, j});
        }
    }
 
    //board의 안전구역을 탐핵한다.
    auto search = [&](int b[MAX][MAX]) -> int {
        int cnt = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (b[i][j] == 0)
                    cnt++;
        return cnt;
    };
 
    //y축인 경우에 0이 아니라면 음수 연산을 취한뒤 변경해주면 4방향으로 회전이 가능하다.
    auto rotate = [&](vector<pair<int, int>> &dir) {
        for (int i = 0; i < dir.size(); i++) {
            if(dir[i].first != 0)
            {
                dir[i].first *= -1;
                dir[i].second *= -1;
                swap(dir[i].first, dir[i].second);
            }
            else
                swap(dir[i].first, dir[i].second);
        }
    };
 
    //방향 값을 가지고 안전구역을 체크한다.
    auto check = [&](int level, int tmpboard[MAX][MAX], vector<pair<int, int>> &dir) {
        pair<int, int> pos = cctv[level];
 
        for (int i = 0; i < dir.size(); i++) {
            int ny = pos.first;
            int nx = pos.second;
            while (1) {
                ny += dir[i].first;
                nx += dir[i].second;
                if (ny < 0 || ny >= n || nx < 0 || nx >= m)
                    break ;
                if(tmpboard[ny][nx] == 6)
                    break ;
                if (tmpboard[ny][nx] == 0)
                    tmpboard[ny][nx] = 23002300;
            }
        }
    };
 
    auto DFS = [&](int level, int b[MAX][MAX], auto &&DFS) -> void {
        if (cctv.size() == level) {
            ret = min(ret, search(b));
            return;
        }
        int cycle = 0;
        vector<pair<int, int>> dir;
 
        if (board[cctv[level].first][cctv[level].second] == 1) { //1번 CCTV인 경우
            cycle = 4;
            dir.push_back({0, 1});
        } else if (board[cctv[level].first][cctv[level].second] == 2) { //2번 CCTV인 경우
            cycle = 2;
            dir.push_back({0, 1}), dir.push_back({0, -1});
        } else if (board[cctv[level].first][cctv[level].second] == 3) { //3번 CCTV인 경우
            cycle = 4;
            dir.push_back({-1, 0}), dir.push_back({0, 1});
        } else if (board[cctv[level].first][cctv[level].second] == 4) { //4번 CCTV인 경우
            cycle = 4;
            dir.push_back({-1, 0}), dir.push_back({0, 1}), dir.push_back({0, -1});
        } else if (board[cctv[level].first][cctv[level].second] == 5) { //5번 CCTV인 경우
            cycle = 1;
            dir.push_back({-1, 0}), dir.push_back({0, 1}), dir.push_back({1, 0}), dir.push_back({0, -1});
        }
 
        int tmpboard[MAX][MAX];
        for (int i = 0; i < cycle; i++) {
            memcpy(tmpboard, b, sizeof tmpboard);
            //방향 값들을 회전 시킨다.
            rotate(dir);
            //보드의 방향으로 감시영역을 체크해준다.
            check(level, tmpboard, dir);
            //다음 CCTV에서 탐색이 가능한 경우를 위해 DFS 탐색에 들어간다.
            DFS(level + 1, tmpboard, DFS);
        }
        return;
    };
 
    DFS(0, board, DFS);
 
    cout << ret << "\n";
    return 0;
}