[algorithm] 백준 - 감시

삼성 SW 기출 문제이며, 꽤나 긴 코드를 요구하는 문제이다.

dfs로 구현했다.

 

CCTV 종류는 총 5가지로, 다음과 같이 회전할 수 있다.

 

 

따라서 방향을 미리 설정해뒀다.

 

pair<int,int> direction[] = {{-1,0}, {1,0}, {0, -1}, {0, 1}};

pair<pair<int,int>,pair<int,int>> secondDirection[] 
= {{{-1,0}, {1,0}},{{0,-1},{0,1}}};

pair<pair<int,int>,pair<int,int>> thirdDirection[]
= {{{-1,0},{0,-1}},{{1,0},{0,1}}, {{1,0},{0,-1}}, {{-1,0},{0,1}}};

tuple<pair<int,int>, pair<int,int>, pair<int,int>> fourthDirection[] 
= {{{-1,0},{0,-1},{1,0}},{{0,-1},{-1,0},{0,1}},{{1,0},{-1,0},{0,1}},{{0,1},{0,-1},{1,0}}};

 

더 나은 방식이 있었을텐데 빨리 풀려고 하다보니 하드코딩이 됐다.

 

그후 dfs로 여러 방향을 비추는 CCTV 조합을 구한다.

 

void dfs(int index){
    if(index == cctvVector.size()){
        int answer = getCount();
        minNum = min(minNum, answer);
        return;
    }
    int copiedMatrix[8][8];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            copiedMatrix[i][j] = matrix[i][j];
        }
    }
    int cctvNum = cctvVector[index];
    switch(cctvNum){
        case 1:
        for(int i = 0; i < 4; i++){
            watchForFirstCCTV(index, i);
            dfs(index + 1);
            copyMap(copiedMatrix);
        }
        break;
        case 2:
        for(int i = 0; i < 2; i++){
            watchForSecondCCTV(index, i);
            dfs(index + 1);
            copyMap(copiedMatrix);
        }
        break;
        case 3:
        for(int i = 0; i < 4; i++){
            watchForThirdCCTV(index, i);
            dfs(index + 1);
            copyMap(copiedMatrix);
        }
        break;
        case 4:
        for(int i = 0; i < 4; i++){
            watchForFourthCCTV(index, i);
            dfs(index + 1);
            copyMap(copiedMatrix);
        }
        break;
        case 5:
            watchForFifthCCTV(index);
            dfs(index + 1);
        break;
    }
}

 

반복문을 돌렸을 때 copyMap을 해야하는데, 함수 호출을 완료 하고,

기존 함수에서 CCTV가 빈 곳(0)을 탐색하기 전 상태로 돌아가기 위한 작업이다.

참고로 탐색하기 전 상태로 돌아가는 것이니 글로벌 변수로 설정하게 되면

호출 완료하기 전 재귀에서 변경될 가능성이 있으므로

글로벌 변수로는 절대로 설정하면 안된다.

 

void copyMap(int copiedMatrix[8][8]){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            matrix[i][j] = copiedMatrix[i][j];
        }
    }
}

 

이제 각 종류의 CCTV가 빈 곳을 어떤 방식으로 탐색하는지 살펴보자.

void watchCCTV(int dx,int dy, int directx, int directy){
    while(1){
        dx += directx;
        dy += directy;
        if(dx < 0 || dx >= n || dy < 0 || dy >= m || matrix[dx][dy] == 6) break;
        if(matrix[dx][dy] == 0){
            matrix[dx][dy] = 7;
        }
    }
}

우선 범위를 벗어나거나 벽(6)을 만나게 될 경우 CCTV가 닿지 않는 공간이므로 탐색을 종료한다.

위에서 언급했던 CCTV 방향을 연속적으로 더하고, 현 위치가 0일 경우

CCTV가 영향을 미치는 공간이므로, 공간의 값을 7로 설정한다.

 

위에서 언급했던 CCTV 방향은 이렇다.

 

pair<int,int> direction[] = {{-1,0}, {1,0}, {0, -1}, {0, 1}};

pair<pair<int,int>,pair<int,int>> secondDirection[]
= {{{-1,0}, {1,0}},{{0,-1},{0,1}}};

pair<pair<int,int>,pair<int,int>> thirdDirection[] 
= {{{-1,0},{0,-1}},{{1,0},{0,1}}, {{1,0},{0,-1}}, {{-1,0},{0,1}}};

tuple<pair<int,int>, pair<int,int>, pair<int,int>> fourthDirection[] 
= {{{-1,0},{0,-1},{1,0}},{{0,-1},{-1,0},{0,1}},{{1,0},{-1,0},{0,1}},{{0,1},{0,-1},{1,0}}};

 

그리고 각 CCTV 별 방향에 대한 탐색을 호출하는 함수를 구현했다.

 

void watchForFirstCCTV(int index, int directionIdx){
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    direction[directionIdx].first,
    direction[directionIdx].second);
}

void watchForSecondCCTV(int index, int directionIdx){
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    secondDirection[directionIdx].first.first,
    secondDirection[directionIdx].first.second);
    
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    secondDirection[directionIdx].second.first,
    secondDirection[directionIdx].second.second);
}

void watchForThirdCCTV(int index, int directionIdx){
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    thirdDirection[directionIdx].first.first,
    thirdDirection[directionIdx].first.second);
    
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    thirdDirection[directionIdx].second.first,
    thirdDirection[directionIdx].second.second);
}

void watchForFourthCCTV(int index, int directionIdx){
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    get<0>(fourthDirection[directionIdx]).first,
    get<0>(fourthDirection[directionIdx]).second);
    
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    get<1>(fourthDirection[directionIdx]).first,
    get<1>(fourthDirection[directionIdx]).second);
    
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    get<2>(fourthDirection[directionIdx]).first,
    get<2>(fourthDirection[directionIdx]).second);
}

 

하드코딩이 되어있기 때문에 좀 더 효율적인 방법을 찾았으면 좋을 거 같다.

 

작성한 코드는 이렇다.

//감시
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
pair<int,int> direction[] = {{-1,0}, {1,0}, {0, -1}, {0, 1}};

pair<pair<int,int>,pair<int,int>> secondDirection[] 
= {{{-1,0}, {1,0}},{{0,-1},{0,1}}};

pair<pair<int,int>,pair<int,int>> thirdDirection[]
= {{{-1,0},{0,-1}},{{1,0},{0,1}}, {{1,0},{0,-1}}, {{-1,0},{0,1}}};

tuple<pair<int,int>, pair<int,int>, pair<int,int>> fourthDirection[] 
= {{{-1,0},{0,-1},{1,0}},{{0,-1},{-1,0},{0,1}},{{1,0},{-1,0},{0,1}},{{0,1},{0,-1},{1,0}}};
int n,m, minNum = 987654321;
int matrix[8][8];
vector<int> cctvVector;
vector<pair<int,int>> cctvVertexVector;
void watchCCTV(int dx,int dy, int directx, int directy){
    while(1){
        dx += directx;
        dy += directy;
        if(dx < 0 || dx >= n || dy < 0 || dy >= m || matrix[dx][dy] == 6) break;
        if(matrix[dx][dy] == 0){
            matrix[dx][dy] = 7;
        }
    }
}
void copyMap(int copiedMatrix[8][8]){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            matrix[i][j] = copiedMatrix[i][j];
        }
    }
}
void watchForFirstCCTV(int index, int directionIdx){
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    direction[directionIdx].first,
    direction[directionIdx].second);
}

void watchForSecondCCTV(int index, int directionIdx){
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    secondDirection[directionIdx].first.first,
    secondDirection[directionIdx].first.second);
    
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    secondDirection[directionIdx].second.first,
    secondDirection[directionIdx].second.second);
}

void watchForThirdCCTV(int index, int directionIdx){
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    thirdDirection[directionIdx].first.first,
    thirdDirection[directionIdx].first.second);
    
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    thirdDirection[directionIdx].second.first,
    thirdDirection[directionIdx].second.second);
}

void watchForFourthCCTV(int index, int directionIdx){
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    get<0>(fourthDirection[directionIdx]).first,
    get<0>(fourthDirection[directionIdx]).second);
    
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    get<1>(fourthDirection[directionIdx]).first,
    get<1>(fourthDirection[directionIdx]).second);
    
    watchCCTV(cctvVertexVector[index].first,
    cctvVertexVector[index].second,
    get<2>(fourthDirection[directionIdx]).first,
    get<2>(fourthDirection[directionIdx]).second);
}
}
int getCount(){
    int count = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(matrix[i][j] == 0){
                count++;
            }
        }
    }
    return count;
}
void dfs(int index){
    if(index == cctvVector.size()){
        int answer = getCount();
        minNum = min(minNum, answer);
        return;
    }
    int copiedMatrix[8][8];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            copiedMatrix[i][j] = matrix[i][j];
        }
    }
    int cctvNum = cctvVector[index];
    switch(cctvNum){
        case 1:
        for(int i = 0; i < 4; i++){
            watchForFirstCCTV(index, i);
            dfs(index + 1);
            copyMap(copiedMatrix);
        }
        break;
        case 2:
        for(int i = 0; i < 2; i++){
            watchForSecondCCTV(index, i);
            dfs(index + 1);
            copyMap(copiedMatrix);
        }
        break;
        case 3:
        for(int i = 0; i < 4; i++){
            watchForThirdCCTV(index, i);
            dfs(index + 1);
            copyMap(copiedMatrix);
        }
        break;
        case 4:
        for(int i = 0; i < 4; i++){
            watchForFourthCCTV(index, i);
            dfs(index + 1);
            copyMap(copiedMatrix);
        }
        break;
        case 5:
            watchForFifthCCTV(index);
            dfs(index + 1);
        break;
    }
}
int main(void){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> matrix[i][j];
            if(matrix[i][j] != 0 && matrix[i][j] != 6){
                cctvVector.push_back(matrix[i][j]);
                cctvVertexVector.push_back({i,j});
            }
        }
    }
    dfs(0);

    cout << minNum;
}