[C++] 백준 15683번: 감시 (구현)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

사무실의 상태와 CCTV의 종류가 주어질 때, 사각 지대의 최소 크기를 구하여라.

---

시간복잡도 어림하기

 미리 시간 복잡도를 어림하는 것이 큰 의미가 없는 구현 문제이므로 생략하겠습니다.

---

알고리즘 설계하기

 우선 문제를 해결하기 위해 필요한 기능부터 정리해봅시다. 문제 해결을 위해 필요한 기능은 크게 두 가지로 정리할 수 있습니다.

1. 각 CCTV 회전
2. 사각 지대 크기 계산

 

 우리는 어떤 CCTV 상태가 최소 사각지대를 만드는지 알 수 없으므로, 결국 모든 경우의 수를 탐색해야합니다. CCTV의 수는 최대 8개 이므로 CCTV 방향의 모든 경우의 수는 4^8 = 2^16 = 65,536으로 제한 시간내에 모든 경우의 수를 탐색하기 적절한 수치입니다.

 따라서 모든 경우를 탐색하는 브루트포스 알고리즘(완전 탐색) 알고리즘을 사용할 수 있습니다.

 

 완전 탐색 알고리즘은 일반적으로 두 가지 영역으로 나누어 구현합니다. 하나는 탐색을 마칠 기저 조건과 다음 탐색을 진행할 탐색 영역으로 나누어 구현합니다.

 

완전 탐색 알고리즘은 다음과 같이 구성할 수 있습니다.

void solve(int idx){
    if(idx == CCTV 최대 수){
        사각지대 크기 계산
        return;
    }
    for(int i = 0; i < 4; i++){
        CCTV 감지 영역 표시
        solve(idx + 1);
        CCTV 감지 영역 원상복구
    }
}

 여기서 idx는 방향을 정할 CCTV를 의미합니다. 탐색을 진행하다 모든 CCTV 탐색을 마치면 더 이상 탐색할 필요가 없으므로 이를 기저조건으로 합니다. 또한, 모든 CCTV 탐색을 마친 후에는 안전 지대의 크기를 구해줍니다.

 아직 탐색을 마치지 않았다면 CCTV를 회전시키면서 탐색을 이어나갑니다. 먼저 현재 CCTV를 회전시키고 다음 CCTV 탐색, 원상 복구 과정을 거치면 모든 CCTV의 모든 방향에 대해 탐색을 마칠 수 있습니다.

 

 각 기능을 하나씩 설계해봅시다.

 

 먼저 사각지대 크기 계산 로직입니다. 이는 단순히 이차원 배열을 탐색하면서 탐색되지 않은 영역을 카운트 하면 됩니다.

 

 가장 핵심 로직은 CCTV 감지 영역을 표시하는 로직입니다. 이 로직은 현재 CCTV의 방향에 대해 탐지 가능한 영역을 표시합니다. 이를 위해서는 CCTV 방향과 CCTV의 좌표 정보가 필요할 것입니다.

 각 방향에 대해 탐색 영역을 표시하는 영역은 공통 코드로 한 번에 나타내기 어려워 각 경우를 나누어 하나씩 지정해주도록 하겠습니다.

 

 마지막으로 표시 영역을 원상 복구하는 로직입니다. 표시된 영역을 다시 원상복구하는 이유는 다음 탐색에 영향을 주지 않도록 하기 위해서입니다. 이때, 원상 복구를 위해서는 변경된 좌표의 위치 정보가 필요합니다. 이는 CCTV 감지 영역을 표시할 때 알 수 있는 값이므로 CCTV 감지 영역  표시 알고리즘이 변경된 좌표들을 반환하도록 하겠습니다. 

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<vector>

#define visited 9;
using namespace std;

int n, m, a[10][10], temp[10][10], ret = 1e9;
vector<pair<int, int>> v;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

/*CCTV 감지 영역 표시*/
vector<pair<int, int>> detect(int idx, int dir){
    vector<pair<int, int>> detected; //변경된 좌표를 저장할 vector
    int y = v[idx].first; //CCTV 처음 y좌표
    int x = v[idx].second; //CCTV 처음 x좌표
    if(a[y][x] == 1){ //한 방향
        while(true){
            int ny = y + dy[dir]; 
            int nx = x + dx[dir]; 
            if(ny >= 0 && ny < n && nx >= 0 && nx < m && a[ny][nx] != 6){
                if(a[ny][nx] == 0){
                    a[ny][nx] = visited; 
                    detected.push_back({ny, nx});
                }
                y = ny; 
                x = nx; 
            }else break;
        }
    }else if(a[y][x] == 2){ //좌우 두 방향
        for(int i = 0; i <= 2; i +=2){
            int _y = y;
            int _x = x;
            while(true){
                int ny = _y + dy[(dir + i) % 4];
                int nx = _x + dx[(dir + i) % 4]; 
                if(ny >= 0 && ny < n && nx >= 0 && nx < m && a[ny][nx] != 6){
                    if(a[ny][nx] == 0){a[ny][nx] = visited; detected.push_back({ny, nx});}
                    _y = ny;
                    _x = nx;
                }else break;
            }
        }
    }else if(a[y][x] == 3){ //90도 두 방향
        for(int i = 0; i < 2; i++){
            int _y = y;
            int _x = x;
            while(true){
                int ny = _y + dy[(dir + i) % 4];
                int nx = _x + dx[(dir + i) % 4];
                if(ny >= 0 && ny < n && nx >= 0 && nx < m && a[ny][nx] != 6){
                    if(a[ny][nx] == 0){ a[ny][nx] = visited; detected.push_back({ny, nx});}
                    _y = ny;
                    _x = nx;
                }else break;
            }
        }
    }else if(a[y][x] == 4){ //세 방향
        for(int i = 0; i < 3; i++){
            int _y = y;
            int _x = x;
            while(true){
                int ny = _y + dy[(dir + i) % 4];
                int nx = _x + dx[(dir + i) % 4];
                if(ny >= 0 && ny < n && nx >= 0 && nx < m && a[ny][nx] != 6){
                    if(a[ny][nx] == 0){ a[ny][nx] = visited; detected.push_back({ny, nx});}
                    _y = ny;
                    _x = nx;
                }else break;
            }
        }
    }else if(a[y][x] == 5){ //네 방향
        for(int i = 0; i < 4; i++){
            int _y = y;
            int _x = x;
            while(true){
                int ny = _y + dy[(dir + i) % 4];
                int nx = _x + dx[(dir + i) % 4]; 
                if(ny >= 0 && ny < n && nx >= 0 && nx < m && a[ny][nx] != 6){
                    if(a[ny][nx] == 0){ a[ny][nx] = 8; detected.push_back({ny, nx});}
                    _y = ny;
                    _x = nx;
                }else break;
            }
        }
    }
    return detected; 
}

void solve(int idx){
    if(idx == v.size()){
        int cnt = 0;
        /*사각 지대 크기 계산*/
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(a[i][j] == 0) cnt++;
            }
        }
        ret = min(cnt, ret);
        return;
    }
    for(int d = 0; d < 4; d++){
        vector<pair<int, int>> detected = detect(idx, d); //CCTV 탐색
        solve(idx + 1);
        for(auto it : detected) a[it.first][it.second] = 0; //원상 복구
    }
}

int main(void){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
            if(a[i][j] != 0 && a[i][j] != 6) v.push_back({i, j}); //CCTV 위치 저장
        }
    }
    solve(0);
    cout << ret;
    return 0;
}

 CCTV 감지 영역을 탐색하는 detect 함수만 살펴보도록 하겠습니다.

 우선 CCTV의 종류를 보고 해당 방향으로 탐색을 진행합니다. 각 CCTV 종류에 대한 탐색은 복잡해 보이지만, 기본 구조는 다음과 같습니다.

1. 최초 위치로 설정
2. 현재 방향에 대해 탐색 시작
 - 벽 또는 사무실의 끝을 만날때까지 탐색 진행
 - 탐색 가능한 지점은 visited(위 코드에서는 9값)로 갱신
3. 1로 돌아가며 다음 방향 탐색

 

 또한, 이 탐색의 핵심은 각 CCTV 종류 별로 적절히 방향 배열에 접근하여 적절한 방향으로 탐색을 진행하는 것입니다. 이를 하드 코딩하여 구현할 수도 있지만, 코드의 양을 줄이기 위해 나머지 연산을 활용하여 구현해주었습니다.

---