BOJ 15683 [감시]

BOJ 감시 : https://www.acmicpc.net/problem/15683

안녕하세요. 이번 문제는 백준 온라인 저지의 감시입니다.

이 문제는 제가 2018년 삼성전자DS 인턴을 지원했을때 겪은 문제인데요,

당시 BFS로 접근했다가 큰 낭패를 봤고, 이번엔 DFS로 접근해봤습니다.

인턴시험때 느낀 것은, 당황하더라도 빠르게 침착함을 유지해야 했다는 것입니다. 

문제 해결과정은 다음과 같습니다.

1. 카메라의 좌표를 vector에 담는다.

2. 각 depth에 해당하는 카메라를 방향마다 설정한다.

3. 모든 카메라를 세팅하면, 감시영역을 설치하고 사각지대 검사.

4. 다시 감시영역을 회수한 뒤, DFS 진행.

#include <iostream>
#include <vector>
using namespace std;
int N, M;
int Map[8][8];
int Result = 0;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
vector<pair<int, int>> camera;
int camera_setting[8][4];
void DFS(int depth);
void Set(int depth, int direction);
void Back(int depth, int direction);
int Calc() {
    int res = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(!Map[i][j])
                res++;
        }
    }
    return res;
}
void DFS(int depth) {
    if(depth == camera.size()) {
        for(int i = 0; i<camera.size(); i++) {
            for(int j=0; j<4; j++) {
                if(camera_setting[i][j]) {
                    Set(i, j+1);
                }
            }
        }
        int temp = Calc();
        if(temp < Result)
            Result = temp;
        for(int i=0; i<camera.size(); i++) {
            for(int j=0; j <4; j++) {
                if(camera_setting[i][j]) {
                    Back(i, j+1);
                }
            }
        }
        return;
    }
    int c_i = camera[depth].first;
    int c_j = camera[depth].second;
    switch(Map[c_i][c_j]) {
        case 1: {
            for(int i=1; i<=4; i++) {
                camera_setting[depth][i-1] = 1;
                DFS(depth + 1);
                camera_setting[depth][i-1] = 0;
            }
            break;
        }
        case 2: {
            for(int i=1; i<=2; i++) {
                camera_setting[depth][i-1] = 1;
                camera_setting[depth][i+1] = 1;
                DFS(depth + 1);
                camera_setting[depth][i-1] = 0;
                camera_setting[depth][i+1] = 0;
            }
            break;
        }
        case 3: {
            for(int i=1; i<=4; i++) {
                camera_setting[depth][i-1] = 1;
                if(i != 4)
                    camera_setting[depth][i] = 1;
                else
                    camera_setting[depth][0] = 1;
                DFS(depth+1);
                camera_setting[depth][i-1] = 0;
                if(i != 4)
                    camera_setting[depth][i] = 0;
                else
                    camera_setting[depth][0] = 0;
            }
            break;
        }
        case 4: {
            for(int i= 1; i<= 4; i++) {
                for(int j= 1; j<=4; j++) {
                    if(i == j)
                        continue;
                    camera_setting[depth][j-1] = 1;
                }
                DFS(depth + 1);
                for(int j= 1; j<=4; j++) {
                    if(i == j)
                        continue;
                    camera_setting[depth][j-1] = 0;
                }
            }
            break;
        }
        case 5: {
            for(int i=1; i<=4; i++)
                camera_setting[depth][i-1] = 1;
            DFS(depth + 1);
            break;
        }
    }
}
void Set(int depth, int direction) {
    int c_i = camera[depth].first;
    int c_j = camera[depth].second;
    int length = 0;
    switch(direction) {
        case 1: {
            length = M - c_j - 1;
            break;
        }
        case 2: {
            length = c_i;
            break;
        }
        case 3: {
            length = c_j;
            break;
        }
        case 4: {
            length = N - c_i - 1;
            break;
        }
    }
    for(int k = 1; k <= length; k++) {
        if(Map[c_i + dx[direction - 1] * k][c_j + dy[direction - 1] * k] == 0) {
            Map[c_i + dx[direction - 1] * k][c_j + dy[direction - 1] * k] = -1;
        }
        else if(Map[c_i + dx[direction - 1] * k][c_j + dy[direction - 1] * k] == 6) {
            break;
        }
    }
}
void Back(int depth, int direction) {
    int c_i = camera[depth].first;
    int c_j = camera[depth].second;
    int length = 0;
    switch(direction) {
        case 1: {
            length = M - c_j - 1;
            break;
        }
        case 2: {
            length = c_i;
            break;
        }
        case 3: {
            length = c_j;
            break;
        }
        case 4: {
            length = N - c_i - 1;
            break;
        }
    }
    for(int k = 1; k <= length; k++) {
        if(Map[c_i + dx[direction - 1] * k][c_j + dy[direction - 1] * k] == -1) {
            Map[c_i + dx[direction - 1] * k][c_j + dy[direction - 1] * k] = 0;
        }
        else if(Map[c_i + dx[direction - 1] * k][c_j + dy[direction - 1] * k] == 6) {
            break;
        }
    }
}
int main() {
    cin >> N >> M;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> Map[i][j];
            if(Map[i][j] != 0 && Map[i][j] != 6)
                camera.push_back(make_pair(i, j));
            else if(Map[i][j] == 0)
                Result++;
        }
    }
    DFS(0);
    cout << Result << endl;
    return 0;
}