[백준/c++] 15683번: 감시

 

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

15683번: 감시

 

 

다른 분들은 어떻게 했는지 모르겠지만, 모든 경우의 수를 받아서 진행했다.

그냥 포기할까 하다가 그래도 2시간은 해봐야지~라는 마음으로 시작했다. 1시간 30분 정도 걸렸다... 흑흑

계속하다 보면 늘지 않을까 싶다.

굉장히 긴 코드가 만들어졌다...^^

 

 

우선, 각 cctv의 감시 범위가 다르기 때문에 그에 따른 함수를 모두 다르게 만들어줬다. 그나마 cctv의 종류가 5개여서 가능했다.

N, M 또한 8 이하여서 충분히 Backtracking으로 된다고 생각했다.

솔직한 마음으론 그냥 중첩 for문으로 만들어버리고 싶었지만^^ 백 트랙킹으로 열심히 해봤다.

1번, 3번, 4번 cctv의 경우 방향이 4가지, 2번 cctv의 경우 2가지, 5번 cctv의 경우 1가지가 나온다.

(2번, 5번은 돌려도 전과 같은 것이 나오므로 중복은 제외했다.)

 

 

순서

1. 사무실에 있는 cctv의 방향을 정한 여러개의 경우의 수 구하기 ⬅️ Backtracking

2. 각 cctv의 정해진 방향으로 감시되는 지역 #(-1)으로 업데이트

3. #(-1)개수 세기

 

 

처음에는, 각 cctv의 방향에 따른 # 값을 셀까 했는데, 모든 cctv가 동시에 감시하므로 동시에 진행되어야 한다.

문제에서 보여준 예시에서 알 수 있다.

만약 따로 #를 진행했다면, 2의 경우 ↔ 방향으로 진행해야 감시하는 부분이 많아진다.

그런데, 3번이 ㄱ 방향으로 감시하는 것이 최대 감시 범위이므로 2와 감시 방향이 겹친다.

그러므로 2번이 ↕ 로 감시하는 것이 더 많은 곳을 감시할 수 있게 된다.

 

위와 같은 이유로 동시에 진행되어야 한다.

vector<int> cctvCase; //시시티비의 순서에 따른 시시번호의 방향
vector<int> cctv; //오피스에 있는 시시티비 번호
vector<pair<int, int>> cctvPos; //시시티비 좌표

이렇게 세가지로 배열을 구성했다. 사실 pair를 사용해서 줄여서 만들 수 있는데, 빠르게 진행하느라 그냥 이렇게 했다..ㅎㅎ

cctvCase: 같은 인덱스의 cctv 방향을 넣을 vector 배열

cctv: 사무실에 있는 cctv 번호

cctvPos: cctv 좌표

 

 

입력받기

cin >> n >> m;
for(int i=0; i<n; i++){
    for(int j=0; j<m; j++) {
        cin >> office[i][j];
        if(office[i][j] == 0) space++;
        else if(office[i][j] >= 1 && office[i][j] <= 5) {
            cctv.push_back(office[i][j]);
            cctvPos.push_back({i, j});
            cctvCnt++;
        }
    }
}

space: 빈 공간 개수 (no cctv, no wall)

cctv라면, cctv에 넣어주고, cctvPos에 좌표를 넣어준다.

 

 

백트래킹으로 경우의 수를 알아보기

최대 방향의 경우의 수가 4이므로 for문을 0..<4 로 진행하되, 2번, 5번 cctv는 4번 회전할 필요가 없다.

그러므로 2번일 경우 3번 이상 회전하면 continue로 넘기고, 5번일 경우 2번 이상 회전하면 continue로 넘긴다.

여기서 tmpOffice에 office의 값을 복사해서 사용한다. 다른 최댓값을 구할 수도 있으니까!

void makeCase(int cnt){ //각 cctv의 방향 정하기
    if(cnt == cctvCnt){ //모든 cctv의 방향 설정함
        //cctvCase를 활용해서 각 cctv의 감시부분 채우기
        for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmpOffice[i][j] = office[i][j];
        for(int i=0; i<cctvCnt; i++){
            switch (cctv[i]) {
                case 1:
                    cctv01(cctvCase[i], cctvPos[i].first, cctvPos[i].second); break;
                case 2:
                    cctv02(cctvCase[i], cctvPos[i].first, cctvPos[i].second); break;
                case 3:
                    cctv03(cctvCase[i], cctvPos[i].first, cctvPos[i].second); break;
                case 4:
                    cctv04(cctvCase[i], cctvPos[i].first, cctvPos[i].second); break;
                case 5:
                    cctv05(cctvPos[i].first, cctvPos[i].second); break;
                default: break;
            }
        }
        //채워진 감시 부분을 제외한 부분 카운팅 -> 최댓값 업데이트
        monitoringSpace = max(monitoringSpace, countingSpace());
        return;
    }
    
    for(int i=0; i<4; i++){ //4방향
        if(cctv[cnt] == 2 && (i == 2 || i == 3)) continue; //cctv2번은 2가지 방향만
        if(cctv[cnt] == 5 && (i == 1 || i == 2 || i == 3)) continue; //cctv5번은 1가지 방향만
        cctvCase.push_back(i);
        makeCase(cnt + 1);
        cctvCase.pop_back();
    }
}

 

 

그리고 cctv의 감시하는 방법이 다르므로, 모두 함수로 만들어줬다.

while문을 통해 벽이거나 사무실을 벗어날때까지 한 방향으로 이동!

cctv1	→	↓	←	↑
cctv2	↑ ↓	←→
cctv3	↑ →	↓ →	← ↓	← ↑
cctv4	← ↑ →	→ ↑ ↓	→ ← ↓	← ↑ ↓
cctv5	→ ← ↑ ↓

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int monitoringSpace = 0;
int space = 0;
int cctvCnt = 0;
int office[9][9]; //0으로 초기화
int tmpOffice[9][9];
vector<int> cctvCase; //시시티비의 순서에 따른 시시번호의 방향
vector<int> cctv; //오피스에 있는 시시티비 번호
vector<pair<int, int>> cctvPos; //시시티비 좌표
//0: 빈칸, 1~5: CCTV, 6: 벽
//감시할 수 있는 영역 (#)

void cctv01(int d, int x, int y){
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int dx = x + dir[d][0]; //다음 위치
    int dy = y + dir[d][1];
    while(0<=dx && dx<n && 0<=dy && dy<m && tmpOffice[dx][dy] != 6) { //범위내 && 벽이 아닌 경우
        if(tmpOffice[dx][dy] == 0) tmpOffice[dx][dy] = -1; //#
        dx = dx + dir[d][0]; //update
        dy = dy + dir[d][1]; //update
    }
}

void cctv02(int d, int x, int y){
    int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int dx1 = x + dir[d][0]; //다음 위치
    int dx2 = x + dir[d+2][0];
    int dy1 = y + dir[d][1];
    int dy2 = y + dir[d+2][1];
    //1
    while(0<=dx1 && dx1<n && 0<=dy1 && dy1<m && tmpOffice[dx1][dy1] != 6) { //범위내 && 벽이 아닌 경우
        if(tmpOffice[dx1][dy1] == 0) tmpOffice[dx1][dy1] = -1; //#
        dx1 = dx1 + dir[d][0]; //update
        dy1 = dy1 + dir[d][1]; //update
    }
    //2
    while(0<=dx2 && dx2<n && 0<=dy2 && dy2<m && tmpOffice[dx2][dy2] != 6) { //범위내 && 벽이 아닌 경우
        if(tmpOffice[dx2][dy2] == 0) tmpOffice[dx2][dy2] = -1; //#
        dx2 = dx2 + dir[d+2][0]; //update
        dy2 = dy2 + dir[d+2][1]; //update
    }
}

void cctv03(int d, int x, int y){
    int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int dx1 = x + dir[d][0]; //다음 위치
    int dx2 = x + dir[(d+1)%4][0];
    int dy1 = y + dir[d][1];
    int dy2 = y + dir[(d+1)%4][1];
    //1
    while(0<=dx1 && dx1<n && 0<=dy1 && dy1<m && tmpOffice[dx1][dy1] != 6) { //범위내 && 벽이 아닌 경우
        if(tmpOffice[dx1][dy1] == 0) tmpOffice[dx1][dy1] = -1; //#
        dx1 = dx1 + dir[d][0]; //update
        dy1 = dy1 + dir[d][1]; //update
    }
    //2
    while(0<=dx2 && dx2<n && 0<=dy2 && dy2<m && tmpOffice[dx2][dy2] != 6) { //범위내 && 벽이 아닌 경우
        if(tmpOffice[dx2][dy2] == 0) tmpOffice[dx2][dy2] = -1; //#
        dx2 = dx2 + dir[(d+1)%4][0]; //update
        dy2 = dy2 + dir[(d+1)%4][1]; //update
    }
}

void cctv04(int d, int x, int y){
    int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int dx1 = x + dir[d][0]; //다음 위치
    int dx2 = x + dir[(d+1)%4][0];
    int dx3 = x + dir[(d+2)%4][0];
    int dy1 = y + dir[d][1];
    int dy2 = y + dir[(d+1)%4][1];
    int dy3 = y + dir[(d+2)%4][1];
    
    //1
    while(0<=dx1 && dx1<n && 0<=dy1 && dy1<m && tmpOffice[dx1][dy1] != 6) { //범위내 && 벽이 아닌 경우
        if(tmpOffice[dx1][dy1] == 0) tmpOffice[dx1][dy1] = -1; //#
        dx1 = dx1 + dir[d][0]; //update
        dy1 = dy1 + dir[d][1]; //update
    }
    //2
    while(0<=dx2 && dx2<n && 0<=dy2 && dy2<m && tmpOffice[dx2][dy2] != 6) { //범위내 && 벽이 아닌 경우
        if(tmpOffice[dx2][dy2] == 0) tmpOffice[dx2][dy2] = -1; //#
        dx2 = dx2 + dir[(d+1)%4][0]; //update
        dy2 = dy2 + dir[(d+1)%4][1]; //update
    }
    //3
    while(0<=dx3 && dx3<n && 0<=dy3 && dy3<m && tmpOffice[dx3][dy3] != 6) { //범위내 && 벽이 아닌 경우
        if(tmpOffice[dx3][dy3] == 0) tmpOffice[dx3][dy3] = -1; //#
        dx3 = dx3 + dir[(d+2)%4][0]; //update
        dy3 = dy3 + dir[(d+2)%4][1]; //update
    }
}

void cctv05(int x, int y){
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for(int i=0; i<4; i++){
        int dx = x + dir[i][0]; //다음 위치
        int dy = y + dir[i][1];
        while(0<=dx && dx<n && 0<=dy && dy<m && tmpOffice[dx][dy] != 6) { //범위내 && 벽이 아닌 경우
            if(tmpOffice[dx][dy] == 0) tmpOffice[dx][dy] = -1; //#
            dx = dx + dir[i][0]; //update
            dy = dy + dir[i][1]; //update
        }
    }
}

int countingSpace(){
    int result = 0;
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(tmpOffice[i][j] == -1) result++;
    return result;
}

void makeCase(int cnt){ //각 cctv의 방향 정하기
    if(cnt == cctvCnt){ //모든 cctv의 방향 설정함
        //cctvCase를 활용해서 각 cctv의 감시부분 채우기
        for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmpOffice[i][j] = office[i][j];
        for(int i=0; i<cctvCnt; i++){
            switch (cctv[i]) {
                case 1:
                    cctv01(cctvCase[i], cctvPos[i].first, cctvPos[i].second); break;
                case 2:
                    cctv02(cctvCase[i], cctvPos[i].first, cctvPos[i].second); break;
                case 3:
                    cctv03(cctvCase[i], cctvPos[i].first, cctvPos[i].second); break;
                case 4:
                    cctv04(cctvCase[i], cctvPos[i].first, cctvPos[i].second); break;
                case 5:
                    cctv05(cctvPos[i].first, cctvPos[i].second); break;
                default: break;
            }
        }
        //채워진 감시 부분을 제외한 부분 카운팅 -> 최댓값 업데이트
        monitoringSpace = max(monitoringSpace, countingSpace());
        return;
    }
    
    for(int i=0; i<4; i++){ //4방향
        if(cctv[cnt] == 2 && (i == 2 || i == 3)) continue; //cctv2번은 2가지 방향만
        if(cctv[cnt] == 5 && (i == 1 || i == 2 || i == 3)) continue; //cctv5번은 1가지 방향만
        cctvCase.push_back(i);
        makeCase(cnt + 1);
        cctvCase.pop_back();
    }
}



int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++) {
            cin >> office[i][j];
            if(office[i][j] == 0) space++;
            else if(office[i][j] >= 1 && office[i][j] <= 5) {
                cctv.push_back(office[i][j]);
                cctvPos.push_back({i, j});
                cctvCnt++;
            }
        }
    }
    makeCase(0);
    cout << space - monitoringSpace << '\n';
    return 0;
}