[백준 알고리즘] 15683번 감시

안녕하세요! 오랜만에 포스팅을 하게 되었네요ㅎㅎ 이번에 풀어본 문제는 2018 상반기 삼성 SW역량 테스트 문제인 감시문제입니다.

15683번: 감시

저도 상반기에 시험봤던 문제인데, 풀지 못했던 문제였는데..ㅠㅠ 다시 푸니까 감회가 새롭네요!!! 이 문제를 풀면서 느낀건 n이 1000 이하의 수라면 n^2의 연산도 매우 짧다는 걸 느꼈습니다.

먼저 문제를 풀기 위해선 중복 순열을 알고 있어야 합니다. 제가 최근에 경우의 수 순열, 조합, 중복 순열에 개념이랑 코드를 포스팅했었습니다.

제가 이 문제를 처음 접근했을 때는 감시 범위가 가장 큰 카메라를 먼저 설정하는 방식으로 문제를 풀었는데, 자꾸 틀렸다고 해서 적용해보았는데 맞더라구요.

이를 중복순열을 적용한다는 건 결국 각 감시 카메라에 대해서 가능한 모든 방향에 대해 판단하라는 것이거든요. 제가 설계한 방향은 이렇습니다.

---

1. 카메라의 개수를 구한 후에 중복 순열을 통해 가능한 방향 조합을 도출
2. 각 방향에 따라 체크해보고 최소값을 구하기.

---

이 문제를 접근할 땐 규칙을 정하는 것도 중요했던 것 같아요. 동, 서, 남, 북의 방향을 어떻게 표현할지 정해놔야 혼동없이 잘 될 것 같습니다.

먼저 중복 순열을 구하는 부분입니다.

vector<int> T;
vector<vector<int>> perm;
int data[4] = {1,2,3,4};
void RP(int n, int r){
    if(r == 0){
        perm.push_back(T);
        return;
    }
    for(int i = n-1; i>=0; i--){
        SWAP(&data[i], &data[n-1]);
        T.push_back(data[n-1]);
        RP(n, r-1);
        T.pop_back();
        SWAP(&data[i], &data[n-1]);
    }
}

구해진 중복순열은 perm이라는 vector에 저장해둡니다. 특이한 부분은 for loop겠네요. swap을 하는 이유는 데이터가 선택 된 것을 표현하기 위해서 인데, 선택하는 데이터를 맨 뒤로 고정시키기 위한 것입니다. 

선택 값을 저장하고, 중복 순열은 중복 값이 허용되니까 같은 배열의 길이와 r-1로 재귀호출이 되겠네요. pop과 다시 swap하는 이유는 for loop가 갱신되면 다른 값을 고르기 위한 것이니까 원래데로 돌려놓는 것이구요. 

 이제 결과를 구하는 부분을 보면

int Solution()
{
    vector<CAMERA> saver;
    scanf("%d %d",&N,&M);
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            scanf("%d",&original[i][j]);
            if((original[i][j]>=1)&&(original[i][j]<=5)) saver.push_back({i,j,original[i][j]});
        }
    }
    RP(4,saver.size()); // 카메라 수 만큼 동,서,남,북 가능하니까 4RPque.size()
    
    int result=10000;
    for(int i=0; i<perm.size(); i++) // 각 방향 벡터에 따라서 경우 실현해봐
    {
        copy(original,map); // 먼저 오리지날 복사
        for(int v=0; v<perm[i].size(); v++)
        {
            CCTV(saver[v].x, saver[v].y, saver[v].type, perm[i][v]); // 설정 방향에 대해서 탐색
        }
        int temp = 0;
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<M; j++)
            {
                if(map[i][j]==0) temp+=1;
            }
        }
        result = (result < temp) ? result : temp;
    }
    return result;
}

전 지도를 전역변수로 선언했기 때문에 케이스마다 원본을 복사해서 체크하는 방식을 사용했습니다. 아까 위에서 구한 중복 순열의 조합을 하나하나 돌면서 체크하는 걸 알 수 있겠네요. 

간단하게 마무리! 전체 코드는 여기입니다! 백준 15683 감사합니다.