[백준][백트래킹][브루트포스] 15683 감시 c++구현

목차

 

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

문제

 

문제 구현 방향

CCTV의 최대 개수는 8개를 넘지 않는다. 이 부분이 핵심 포인트였다... 문제를 제대로 읽지 않고 완전 탐색 불가능한거 아니야? 하면서 그리디로 돌아갔다가 한참 헤맸다 ㅜ 문제는 꼼꼼히 읽어야 된다.

 

 

문제 아이디어

그냥 백트래킹 잘 해주면 풀린다. 아이디어는 복구를 하기 위한 좌표를 저장해 놓고 저장해 놓은 좌표를 바탕으로 복구하면 된다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>


using namespace std;

//cctv 구조체
typedef struct CCTV {
    int num;
    int x;
    int y;
}CCTV;

//상 하 좌 우
int dx[4] = {0,0,-1, 1};
int dy[4] = {-1, 1,0,0};

int N, M;
int msum = 0;
vector<CCTV> v;

//마지막 카운트 해주는 함수
int counting(char board[9][9]) {
    int sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] != '0')
                sum++;
        }
    }
    return sum;
}

//방향이 주어지면 끝까지 탐색하는 함수
void searching(int nx, int ny, vector<pair<int, int>>&restore, char board[9][9], int direct) {
    while (true) {
        nx += dx[direct];
        ny += dy[direct];
        if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1)break;
        if (board[ny][nx] == '6')break;
        if (board[ny][nx] == '0') {
            board[ny][nx] = '#';
            restore.push_back({ nx, ny });
        }
    }
}

//다시 복구해주는 함수
void repair(vector<pair<int, int>>&restore, char board[9][9]) {
    for (auto p : restore) {
        board[p.second][p.first] = '0';
    }
}

//백트래킹을 통한 탐색
void dfs(int idx, char board[9][9]) {
    if (idx == v.size() ) {
        msum = max(msum, counting(board));

        return;
    }
    int x = v[idx].x;
    int y = v[idx].y;
    int nx = x;
    int ny = y;

    if (v[idx].num == '1') {
        for (int i = 0; i < 4; i++) {
             nx = x;
            ny = y;
            vector<pair<int, int>> restore;
            searching(nx, ny, restore, board, i);
            dfs(idx + 1, board);
            repair(restore, board);
        }
    }
    else if (v[idx].num == '2') {
    
        vector<pair<int, int>> restore;
        for (int i = 0; i < 2; i++) {
            if (i == 0) {
                searching(nx, ny, restore, board, 2);
                nx = x;
                ny = y;
                searching(nx, ny, restore, board, 3);
                dfs(idx + 1, board);
                repair(restore, board);
            }
            else {
                searching(nx, ny, restore, board, 0);
                nx = x;
                ny = y;
                searching(nx, ny, restore, board, 1);
                dfs(idx + 1, board);
                repair(restore, board);
            }
        }
    }
    else if (v[idx].num == '3') {
    
        vector<pair<int, int>> restore;
        for (int i = 0; i < 4; i++) {
            if (i == 0) {
                searching(nx, ny, restore, board, 0);
                nx = x;
                ny = y;
                searching(nx, ny, restore, board, 3);
                dfs(idx + 1, board);
                repair(restore, board);
            }
            else if(i==1){
                searching(nx, ny, restore, board, 3);
                nx = x;
                ny = y;
                searching(nx, ny, restore, board, 1);
                dfs(idx + 1, board);
                repair(restore, board);
            }
            else if (i == 2) {
                searching(nx, ny, restore, board, 1);
                nx = x;
                ny = y;
                searching(nx, ny, restore, board, 2);
                dfs(idx + 1, board);
                repair(restore, board);
            }
            else {
                searching(nx, ny, restore, board, 2);
                nx = x;
                ny = y;
                searching(nx, ny, restore, board, 0);
                dfs(idx + 1, board);
                repair(restore, board);
            }
        }
    }
    else if (v[idx].num == '4') {
      
        vector<pair<int, int>> restore;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                nx = x;
                ny = y;
                if(i !=j)
                    searching(nx, ny, restore, board, j);
            }
            dfs(idx + 1, board);
            repair(restore, board);
        }
    }
    else {

        vector<pair<int, int>> restore;
        for (int i = 0; i < 4; i++) {
                nx = x;
                ny = y;
                searching(nx, ny, restore, board, i);
        }
        dfs(idx + 1, board);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    char board[9][9] = { '0' };
    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] != '0' && board[i][j] != '#' && board[i][j]!= '6') {
                v.push_back({ board[i][j], j, i });
            }
        }
    }
    dfs(0, board);
    cout << N*M-msum;
    


    return 0;
}