백준, BOJ, 15683번 C++ [CPP] **

음.. 전형적인 구현 문제로

말하는 대로 구현하면 된다.

구현에 무엇을 쓸 지는 모두 사용자의 맘대로

다만 시간보다 메모리는 많기에 맘껏 써도 될 것 같다.

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

15683번: 감시

 

---

 

이건 내가 한 번에 못풀었다.

감은 왔는데 도저히 구현이 되질 않았다.

 

하지만 풀이를 보니.. 30%정도까지는 맞았더라..

백트래킹을 써야지~ 생각은 했지만 백트래킹에서 탐색을 하지 못했다.

 

#맞은 풀이(참고해서)

#include<iostream>

using namespace std;


int ans; //답
int col, row; // 행 렬
int office[8][8]; // 입력받음

// 카메라, 좌표와 타입
struct CAM{
    int x, y, type;
};

CAM cam[8]; // 카메라 정보 (최대 8개)
int CAM_SIZE = 0; //  카메라 개수
int rot_type[5] = {4,2,4,4,1}; // 가능한 회전 횟수


//직접 카메라를 탐색 일자로 탐색, 방향별로 다름.
void update(int dir, CAM c){
    dir %= 4;
    if(dir == 0){
        //동쪽
        for(int y = c.y + 1; y<row; y++){  
            if(office[c.x][y] == 6) break;
            office[c.x][y] = -1;
        }
    }
    if(dir == 1){
        //북
        for(int x = c.x - 1; x>= 0; x--){  
            if(office[x][c.y] == 6) break;
            office[x][c.y] = -1;
        }
    }
    if(dir == 2){
        //서
        for(int y = c.y - 1; y >= 0; y--){  
            if(office[c.x][y] == 6) break;
            office[c.x][y] = -1;
        }
    }
    if(dir == 3){
        //남
        for(int x = c.x + 1; x < col; x++){  
            if(office[x][c.y] == 6) break;
            office[x][c.y] = -1;
        }
    }
}


// 카피하는 함수
void copy(int copied[8][8], int origin[8][8]){
      for(int i = 0; i<col; i++){
        for(int j = 0; j<row; j++){
            copied[i][j] = origin[i][j];
        }
    }
}



void search(int cam_idx){ // 카메라를 차례대로 탐색 (백트래킹)
    //모두 탐색
    if(cam_idx == CAM_SIZE){
        // 최소 넓이 탐색
        int w = 0;
        for(int i = 0; i<col; i++){
           for(int j = 0; j<row; j++){
                if(office[i][j] == 0){
                    w++;
                }
            }
        }
        if(ans> w){
            ans = w;
        }
        return;
    }

    int backup[8][8]; // map을 백업해둠
    int type = cam[cam_idx].type; // 타입을 인덱스를 이용하여 받아옴
    
    //모든 방향을 하나하나 탐색하기 위함
    for(int dir = 0; dir<rot_type[type]; dir++){
        //office를 직접 탐색할 것이므로 백업해둠.
        copy(backup, office);
         //1번 카메라.
        if(type == 0){
            update(dir, cam[cam_idx]);
        }
        if(type == 1){
            update(dir, cam[cam_idx]);
            update(dir+2, cam[cam_idx]);
        }
        if(type == 2){
            update(dir, cam[cam_idx]);
            update(dir+1, cam[cam_idx]);
        }
        if(type ==3){
            update(dir, cam[cam_idx]);
            update(dir+1, cam[cam_idx]);
            update(dir+2, cam[cam_idx]);            
        }
        if(type == 4){
            update(dir, cam[cam_idx]);
            update(dir+1, cam[cam_idx]);
            update(dir+2, cam[cam_idx]);
            update(dir+3, cam[cam_idx]);
        }
        search(cam_idx+1);
        // 해당 인덱스에서 전 인덱스로 돌아가 다시 탐색하기 위해 초기화
        copy(office, backup);
        
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> col >> row;
    
    for(int i = 0; i<col; i++){
        for(int j = 0; j<row; j++){
            //map 정보 입력
            cin>> office[i][j];
            //카메라에 대한 정보 입력
            if(office[i][j] != 0 && office[i][j] != 6){
                cam[CAM_SIZE].x = i;
                cam[CAM_SIZE].y = j;
                cam[CAM_SIZE].type = office[i][j] -1; // 1번타입은 rot_type의 0번 인덱스 이기 때문
                CAM_SIZE++;
            }
        }
    }
    ans = 100;
    search(0);
    cout << ans ;
}

 

사실 무엇을 구현해야 할 지 안다면 그것은 그렇게 어렵지 않다.

구현 문제가 어려운 이유는

~을 구현하기 위해 필요한 것이 무엇인지 정확하게 파악을 못하기 때문이다.

 

내가 그랬다.

 

우선 문제를 보고 생각해보자.

 

1. 입력되는 것.

행과 열 그리고 사무실의 구조가 입력된다.

1-1 사무실의 구조에서 입력되는 것, (카메라, 벽, 공간) 

 

 

2. 구해야하는 것

카메라가 감시하지 못하는 공간의 최소 넓이

 

 

3. 구하기 위한 방법

3-1 입력 받은 모든 카메라에 대해서 감시 공간을 설정해야함 (**이게 제일 어렵다)

3-2 모든 카메라에 대해서 감시 공간을 설정했으면  감시되지 않는 공간을 계산

3-3 기존 가지고 있는 값보다 작으면 갱신

 

---

 

즉, 카메라를 기준으로 우리가 받은 사무실의 구조에 감시공간을 표시해야한다는 말이다.

백트래킹을 하면서 모조리 뒤져보면 되겠다고 생각했다.

 

기본적으로 백트래킹은 재귀를 바탕으로 

아래와 같은 꼴이 일반적이다.

---

void search(int k)  // 일반적으로 k는 현재 선택한 개수 꼴을 가짐
if(k == 입력받은 카메라 개수){
//현재 만들어진 사무실에서 감시되지 않는 부분 계산
~~
//현재 최솟값 보다 작으면 갱신

return; //함수 종료
}

차례대로 넣어야 한다.
for( cctv의 타입마다 회전 수가 다름. 우선 타입이 다르므로 타입별로 입력){
//office를 사용하기 전에 복사를 해놓아야함.(백업) - > decision tree에서 전 상태로 돌리기 위함

// 다음 선택으로 넘어감 

// 복원 -> 전 상태로 
}

 

---

 

위와 같이 정도로 되겠다.

 

3-1이 좀 어렵다.

카메라를 입력받아서 사용하는데

카메라의 타입이 5개 회전을 4번이나 할 수 있다.

즉, 카메라를 받아서 office를 탐색하는 과정을 구현하기가 어렵다.

이것은 ... 많은 연습이 필요하다.

 

나는 안보고 내가 짤 수 있을 때까지... 한 번 시도해보려고 한다.

 

아무튼 내 의식의 흐름에 따라 문제를 보았는데.. 이 정도면 미래의 나에게도 아이디어를 줄 수 있을 것 같다.