[DFS] 15683번 감시

15683번 감시

 

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

 

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 벽을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

 

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

 

예제 입력

4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

6 6
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

6 6
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1

6 6
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 5 0 0
0 0 5 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1

1 7
0 1 2 3 4 5 6

3 7
4 0 0 0 0 0 0
0 0 0 2 0 0 0
0 0 0 0 0 0 4

 

예제 출력

20

15

6

2

0

0

 

해결방법

모든 경우를 DFS+백트래킹을 통해 전부 탐색해보는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

생각보다 무식한 방법(?)으로 문제를 해결했다

CCTV를 모두 벡터에 넣은 다음 DFS를 통해 모든 경우의 사각지대를 구해 최소값을 갱신했다

 

1. 각 cctv 의 방향을 모두 설정한다

   • 여기서는 재귀 함수를 통해 모든 cctv 인덱스로 접근해 방향을 설정해준다
   • 2번과 5번 cctv는 각각 2개, 1개의 경우의 수가 존재하므로 예외처리를 해준다

2. 설정한 방향대로 모든 cctv를 작동시킨다

   • 1~5 종류의 cctv 별로 조건문을 통해 감시를 퍼뜨린다
   • 해당 방향의 일직선으로 퍼지는 함수를 준비해 종류별로 사용한다

3. 모든 cctv의 방향대로 작동시킨 후, 사각지대를 구하여 최소값을 갱신한다

   • cctv를 모두 작동시킨 후, 아직 값이 0 인 부분을 구하여 사각지대의 수를 구한다

 

먼저 이 문제는 부분순열로 접근하면 안된다

왜냐하면 모든 cctv는 방향이 설정되야하기 때문이다

만약 CCTV가 1 2 3 4 가 존재한다고 가정해보자

이 때, 4번 cctv를 제외한 나머지 cctv만 방향을 설정한다면???

이 경우는 성립될 수 없다

따라서 dfs 함수에서 cctv 벡터를 도는 것이 아니라 dfs 함수 하나 당, 하나의 cctv와 연관이 있는 것이다

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 9
#define INF 987654321
using namespace std;

typedef pair<int, int> node;

int n,m,ans,cctv_cnt;
int map[MAX][MAX];
int tmp[MAX][MAX];
int cctv_dir[MAX];

// 동 서 남 북
int dx[5] = {0,0,0,1,-1};
int dy[5] = {0,1,-1,0,0};

vector<node> cctv;

// cctv 의 감시범위를 퍼뜨리기 위한 임시 map
void copyMap(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            tmp[i][j] = map[i][j];
        }
    }
}

// 해당 좌표부터 원하는 방향까지 감시범위를 구하는 함수
// 맵의 끝에 도달하거나 벽을 만나기 전까지 퍼짐
void detect(int x,int y,int d){
    int nx = x;
    int ny = y;
    
    while(true){
        nx += dx[d];
        ny += dy[d];
        
        if(nx<0 || ny<0 || nx>=n || ny>=m) break;
        
        // 빈 칸이라면 cctv의 감시범위임
        if(tmp[nx][ny] == 0){
            tmp[nx][ny] = 7;
        }
        // 벽이라면 감시 종료
        else if(tmp[nx][ny] == 6){
            break;
        }
    }
}

// 모든 cctv를 설정한 방향대로 감시
// 1~5 종류에 따라 detect 함수를 다르게 사용함
void set_cctv(){
    for(int i=0; i<cctv.size(); i++){
        int x = cctv[i].first;
        int y = cctv[i].second;
        
        switch (tmp[x][y]) {
            case 1:
            {
                // 동 서 남 북 中 한방향
                int dir = cctv_dir[i];
                detect(x,y,dir);
                break;
            }
                
            case 2:
            {
                if(cctv_dir[i] == 1){
                    // 동 서
                    detect(x,y,1);
                    detect(x,y,2);
                }else{
                    // 남 북
                    detect(x,y,3);
                    detect(x,y,4);
                }
                break;
            }
            case 3:
            {
                if(cctv_dir[i] == 1){
                    // 동 북
                    detect(x,y,1);
                    detect(x,y,4);
                }else if(cctv_dir[i] == 2){
                    // 동 남
                    detect(x,y,1);
                    detect(x,y,3);
                }else if(cctv_dir[i] == 3){
                    // 서 남
                    detect(x,y,2);
                    detect(x,y,3);
                }else if(cctv_dir[i] == 4){
                    // 서 북
                    detect(x,y,2);
                    detect(x,y,4);
                }
                break;
            }
            case 4:
            {
                if(cctv_dir[i] == 1){
                    // 동 서 북
                    detect(x,y,1);
                    detect(x,y,2);
                    detect(x,y,4);
                }else if(cctv_dir[i] == 2){
                    // 동 남 북
                    detect(x,y,1);
                    detect(x,y,3);
                    detect(x,y,4);
                }else if(cctv_dir[i] == 3){
                    // 동 서 남
                    detect(x,y,1);
                    detect(x,y,2);
                    detect(x,y,3);
                }else if(cctv_dir[i] == 4){
                    // 서 남 북
                    detect(x,y,2);
                    detect(x,y,3);
                    detect(x,y,4);
                }
                break;
            }
            case 5:
            {
                // 동 서 남 북
                detect(x,y,1);
                detect(x,y,2);
                detect(x,y,3);
                detect(x,y,4);
                break;
            }
                
            default:
                break;
        }
    }
}

// 사각지대를 구하는 함수
int getBlindSpot(){
    int res = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(tmp[i][j] == 0) res++;
        }
    }
    return res;
}

// 모든 cctv에 대해 방향을 설정하도록 재귀함수 구현
// 만약 cctv 개수만큼 인덱스가 도달했다면 cctv 감시를 퍼뜨린 후
// 사각지대를 구해 최소값을 갱신함
void dfs(int ind,int cnt){
    // 모든 cctv의 방향을 설정했다면
    if(cnt == cctv.size()){
        // tmp 배열을 만듬
        copyMap();
        
        // cnt개의 cctv의 감시를 퍼뜨림
        set_cctv();
        
        // 최소값 찾기
        ans = min(ans,getBlindSpot());
        return;
    }
    
    int x = cctv[ind].first;
    int y = cctv[ind].second;
    
    // cctv 방향 설정
    for(int k=1; k<=4; k++){
        // 2번과 5번은 각각 2개, 1개의 방향만 존재하므로 예외 처리
        if(map[x][y] == 5 && k > 1) continue;
        if(map[x][y] == 2 && k > 2) continue;
        
        cctv_dir[ind] = k;
        dfs(ind+1,cnt+1);
        cctv_dir[ind] = 0;
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
            
            // cctv 의 좌표를 벡터에 넣는다
            if(map[i][j] >= 1 && map[i][j] <= 5)
                cctv.push_back(node(i,j));
        }
    }
    
    ans = INF;
    dfs(0,0);
    cout << ans << "\n";
    
    return 0;
}