[C++][프로그래머스] 외벽 점검 - 완전탐색

문제

https://programmers.co.kr/learn/courses/30/lessons/60062

 

풀이

외벽 점검을 위해 최소로 투입해야 하는 친구의 수를 구하는 문제였습니다.dist의 크기가 1 이상 8 이하로 매우 작기 때문에 완전탐색 방식으로 풀었습니다.

 

dist가 [1, 2, 3, 4]와 같을 때길이 4를 이동할 수 있는 친구를 1명 투입해보고 모든 취약점 점검이 불가능하다면 추가로 길이 3을 이동할 수 있는 친구를 1명 투입해보고 모든 취약점 점검이 불가능하다면 

추가로 길이 2를 이동할 수 있는 친구를 1명 투입해보는 작업을 모든 취약점 점검이 가능할때까지 반복하였습니다.

 

1단계에서 투입인원을 정하게 되면

 

투입인원을 배치하는 순서에 따라 모든 취약점을 커버할 수도, 커버하지 못할 수도 있기 때문에

2단계에서는 해당 인원의 순열을 구하게 됩니다.(저는 dfs를 이용하였습니다) 

 

3단계에서는 각 case에 대해 실제로 모든 취약점을 커버할 수 있는지 확인하게 됩니다.

이 때 모든 week 지점의 각 요소에 대해 배치해가며 확인합니다.

 

예를 들어 순열이 [4, 2]인 경우 아래와 같이 배치할 수 있습니다. 

3개의 case에서는 모든 취약점을 커버할 수 없지만

마지막 case에서는 모든 취약점을 커버할 수 있게 됩니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N;
bool check[10];
int tmp[10];
bool flag = false;
vector<int> Weak;

int getDistance(int s, int e) {
	return Weak[e] - Weak[s] < 0 ? Weak[e] - Weak[s] + N : Weak[e] - Weak[s];
}

bool isAllCovered(bool isCovered[20]) {
	bool isAllCoveredFlag = true;
	for (int j = 0; j < Weak.size(); j++) {
		if (isCovered[j] == false) {
			isAllCoveredFlag = false;
		}
	}
	return isAllCoveredFlag;
}

void clear() {
	for (int i = 0; i < 10; i++) {
		check[i] = false;
		tmp[i] = 0;
	}
	flag = false;
}

void dfs(int x, int n, vector<int> man) {
	if (x >= n) {
		for (int i = 0; i < Weak.size(); i++) {
			bool isCovered[20] = { false, };
			int manIdx = 0;
			int s = i;
			int e = (s + 1) % Weak.size();

			while (true) {
				isCovered[s] = true;
				if (getDistance(s, e) <= man[tmp[manIdx]]) {
					isCovered[e] = true;
					e = (e + 1) % Weak.size();
				}
				else {
					s = e;
					e = (s + 1) % Weak.size();
					manIdx++;
				}
				if (isAllCovered(isCovered)) {
					flag = true;
					return;
				}
				if (manIdx >= n) {
					break;
				}
			}
		}
	}
	else {
		for (int i = 0; i < n; i++) {
			if (check[i] == false) {
				check[i] = true;
				tmp[x] = i;
				dfs(x + 1, n, man);
				check[i] = false;
				tmp[x] = 0;
				if (flag) return;
			}
		}
	}
}

int solution(int n, vector<int> weak, vector<int> dist) {
	Weak = weak;
	N = n;

	sort(dist.begin(), dist.end());
	vector<int> man;
	for (int i = dist.size() - 1; i >= 0; i--) {
		man.push_back(dist[i]);
		int cnt = man.size();

		clear();

		// man N명에 대한 순열
		dfs(0, cnt, man);
		if (flag) return cnt;
	}

	return -1;
}

int main() {
	int n = 200;
	vector<int> weak = { 0, 10, 50, 80, 120, 160 };
	vector<int> dist = { 1, 2, 3, 4 };
	cout << solution(n, weak, dist);

	return 0;
}