[BaekJoon/백준] 15683번 감시

 

아무쪼록 내가 제 시간에 풀 수 있는 문제는 절대 아니였다.

 

풀이를 찾아봤는데도, 해석하여 푸는데도 오래걸렸고, 반례를 찾아내는데에도 오래걸렸다.

 

요 근래 문제를 풀면서 가장 오랜 시간을 사용했다.

 

 

 

문제에는 백트래킹 개념을 사용했다.

 

이 때, 내 풀이에 있어서 문제에서 주의할 점은

 

각 카메라가 감시하는 영역을 모두 동일한 값으로 해주면

예를들어 첫번째 카메라가 9라는 숫자로 감시영역 표시를 해줬는데

세번째 카메라가 dfs를 돌다가, 감시 해제를 통해 토글을 했는데 해당 부분이 이미 첫번쨰 카메라가 감시하는 부분을 지워버릴 수 있다.

 

따라서 방법은 두 가지가 있다.

 

 

1. 아래와 같은 방식을 사용하면서,

VISIT[i] = true;
dfs();
VISIT[i] = false;

각 카메라(x번째 카메라)가 감시하는 영역에 대한 의미를 다르게 부여한다.

 

ex) 첫 번째 카메라의 감시 영역은 'a'로 표시, 두 번째 카메라의 감시 영역은 'b'로 표시..

 

이렇게 하면, 다른 카메라가 또다른 카메라의 감시 영역을 토글 과정에서 지우는 과정을 피할 수 있다

 

 

2. 위와 같은 형식을 사용하는 대신

 

재귀 dfs 시작 전에 아예 맵 전체를 통째로 백업해놓은 뒤에, 적용하고 다시 복구한다. 그럼 문제가 해결될 수 있다.

 

두 방법 다 마찬가지로 백트래킹(뒤로 돌아가서 탐색)의 의미로써 토글의 의미는 같지만, 그 구현 방법이 다른 것이다.

이 방법은 이 블로그에 매우 잘 정리되어 있다.

 

 

나는 첫 번째 방법을 사용했다.

/*
 
 조합 형식이므로 visit 체크 미필요.
 
 1번 카메라는 a로 감시영역 표시
 2번 카메라는 b로 감시영역 표시
 ..
 
 이렇게 구분해줘야, 나중에 감시영역을 동일하게 했을 떄 백트래킹 토글 시
 다른 카메라가 체크해놓은 부분을 토글하는 불상사를 막을 수 있다.
 
 */


#include <iostream>
#include <vector>
#define MIN(a, b) ((a<=b)?a:b)

using namespace std;

vector<pair<int, pair<int ,int>>> CAMERA;
int C_SIZE; // CAMERA 벡터 사이즈

char MAP[8][8];


// 동 북 서 남
int mx[4] = {0, -1, 0, 1};
int my[4] = {1, 0, -1, 0};

int N, M;

int MIN_VAL = 100;

void EVALUATE() {

    int c = 0;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            if(MAP[i][j] == '0')
                c++;
        }
    }
    
    MIN_VAL = MIN(MIN_VAL, c);
}

void check(int i, int direction, int x, int y, bool check) {
    
    
    direction %= 4;
    
    int tx = x;
    int ty = y;
    
    while(1) {
                
        tx += mx[direction];
        ty += my[direction];

        if(tx < 0 || tx >= N || ty < 0 || ty >= M)
            break;
        
        if(MAP[tx][ty] == '6')
            break;
                    
        
        if((MAP[tx][ty] == 'a' + i) || MAP[tx][ty] == '0') {
            
            if(check)
                MAP[tx][ty] = 'a' + i;
            else
                MAP[tx][ty] = '0';
        }
    }
}

void dfs(int start) {
    
    if(start == C_SIZE) {
        
        EVALUATE();
        
        return;
        
    }
    
    for(int i = start; i < C_SIZE; i++) {
        
        
        for(int k = 0; k < 4; k++) { // 통일성을 위해 4 방향에 대해 최대로 반복해본다.
            
            
            switch(CAMERA[i].first) {
                    
                case '1':
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, true);
                    
                    dfs(i + 1);
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, false);
                    
                    break;
                    
                case '2':
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, true);
                    check(i, k + 2, CAMERA[i].second.first, CAMERA[i].second.second, true);

                    
                    dfs(i + 1);
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, false);
                    check(i, k + 2, CAMERA[i].second.first, CAMERA[i].second.second, false);

                    
                    break;
                    
                case '3':
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, true);
                    check(i, k + 1, CAMERA[i].second.first, CAMERA[i].second.second, true);

                    
                    dfs(i + 1);
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, false);
                    check(i, k + 1, CAMERA[i].second.first, CAMERA[i].second.second, false);

                    
                    break;
                    
                case '4':
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, true);
                    check(i, k + 1, CAMERA[i].second.first, CAMERA[i].second.second, true);
                    check(i, k + 2, CAMERA[i].second.first, CAMERA[i].second.second, true);

                    
                    dfs(i + 1);
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, false);
                    check(i, k + 1, CAMERA[i].second.first, CAMERA[i].second.second, false);
                    check(i, k + 2, CAMERA[i].second.first, CAMERA[i].second.second, false);

                    
                    break;
                    
                case '5':
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, true);
                    check(i, k + 1, CAMERA[i].second.first, CAMERA[i].second.second, true);
                    check(i, k + 2, CAMERA[i].second.first, CAMERA[i].second.second, true);
                    check(i, k + 3, CAMERA[i].second.first, CAMERA[i].second.second, true);

                    
                    dfs(i + 1);
                    
                    check(i, k, CAMERA[i].second.first, CAMERA[i].second.second, false);
                    check(i, k + 1, CAMERA[i].second.first, CAMERA[i].second.second, false);
                    check(i, k + 2, CAMERA[i].second.first, CAMERA[i].second.second, false);
                    check(i, k + 3, CAMERA[i].second.first, CAMERA[i].second.second, false);


                    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] >= '1' && MAP[i][j] <= '5') {// 카메라의 종류와 위치정보를 담아준다.
                CAMERA.push_back({MAP[i][j], {i, j}});
            }
        }
    }
    
    C_SIZE = CAMERA.size();
    
    
    dfs(0);
    
    
    cout << MIN_VAL << "\n";
    
    
}

 

코드에 아쉬운 점이 있다면,

 

코드의 통일성을 위해, 모든 case에 대해 for문을 4번씩 반복한다는 것이다.

case '5'와 같은 경우는 회전할 필요가 없다. 결국 상하좌우이기 때문에.

 

 

소요 시간 : 3시간 30분