[프로그래머스/C++] 외벽 점검 (2020 KAKAO BLIND RECRUITMENT)

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 완전탐색으로 풀 수 있는 문제다.

 

시계방향으로 점검을 하나 시계 반대 방향으로 점검을 하나 어차피 이동하는 거리는 같기 때문에 시계 방향으로 도는 경우만 고려하면 된다.

 

여기서 완전 탐색을 할 때 weak 부분에서 점검을 시작하는게 이득이다. 이 점을 고려해서 특정 weak 부분에서 어떤 weak까지 점검을 할 수 있는지 비교하면된다.

마지막 취약점 부분까지 탐색을 완료하면 탐색을 마쳤을 경우 이때 출발한 친구 수를 min값과 비교해 저장하면 된다.

 

여기서 또 출발을 어디서부터 하는지 생각해야 한다. 왜냐하면 계산을 편하게 하기 위해 시계 반대 방향의 탐색을 고려하지 않고 시계 방향으로 탐색만 고려했기 때문이다.

 

그래서 첫 친구가 출발하는 위치에 따라 탐색 결과 값이 달라지기 때문에 이를 고려해 처음 출발하는 위치를 weak수 만큼 바꿔주면서 탐색해야한다.

 

이렇게 완전 탐색을 할 경우 약 8!*15(출발점) 의 연산으로 끝낼 수 있을 것이다.

​

[아이디어 정리]

1. 취약점에서 어떤 친구가 출발할 지 완전탐색(DFS)로 구한다.
2. 만약 모든 취약점을 탐색했다면, 출발하는 친구의 수를 비교하고 최솟값을 저장한다.
3. 첫 출발점을 바꿔 다시 완전 탐색하는 1, 2번 과정을 반복한다.
4. min 값을 return한다.

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int minAns=17;
void Calc(vector<int> &weak, vector<int> &dist, vector<bool>visitedD, int weakIdx, int cnt)
{
    if (cnt+1>minAns)
    {
        return;
    }
    for (int i=0; i<dist.size(); i++) //탐색
    {
        int pidx=1;
        if (!visitedD[i]) //방문한 적이 없다면
        {  ///0, 1 , size=1
            while (weakIdx+pidx<weak.size())
            {
                if (weak[weakIdx]+dist[i]<weak[weakIdx+pidx]) 
                {
                    break;
                }
                pidx++;
            }
            if (weakIdx+pidx==weak.size())
            {
                if (minAns>cnt+1)
                {
                    minAns=cnt+1;
                }
                return;
            }
            visitedD[i]=true;
            Calc(weak, dist, visitedD,weakIdx+pidx,cnt+1);
            visitedD[i]=false;
        }
    }
}

int solution(int n, vector<int> weak, vector<int> dist) {
    // 완전탐색
    vector<bool> visited;
    sort(dist.begin(),dist.end(), [](int a, int b){ return a>b;});
    vector<int> rotWeak(weak.size(),0);    
    for (int i=0; i<weak.size(); i++)
    {
        int minus=weak[i];
        for (int j=0; j<weak.size(); j++)
        {
            rotWeak[j]=(weak[j]+(n-minus))%n; // 시작 방향 바꾸는 방법
        }
        sort(rotWeak.begin(),rotWeak.end());
        visited = vector<bool>(dist.size(), false);
        Calc(rotWeak, dist, visited, 0, 0);
    }
    return minAns==17?-1:minAns;
}

 

---

 

다른 사람의 풀이를 보다 보니, 출발점을 바꾸는 방법은 weak에 n만큼 더해 단순히 배열의 길이를 늘리는 방법도 있었다.

처음에 코드를 작성할 때, 출발점을 바꾸는 방법을 잘못 작성해서 제대로 된 완전 탐색이 안됐었다... ㅠㅠㅠ

 

프로그래머스