[Programmers] 외벽 점검

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

2020 카카오 BLINE RECRUITMENT

---

백트레킹 backtracking 완전탐색 complete search

● Input 크기가 크지 않으므로, 모든 경우에 대해서 완전탐색을 진행하면 됩니다.

● 우리는 어떤 친구를 어떤 지점에 배치할지, 그 후 시계 방향 혹은 반 시계 방향 중 어떤 방향으로 보내지를 고려해야 된다. 이때, 외벽이 원형 상태인 점을 이용하여 Weak 배열( 배치해야 되는 지점 ) 을 다음과 같이 하나씩 뒤로 보내본다면 ( 어떤 지점에 배치 + 어떤 방향 ) 이 한 번에 해결된다.

예를 들어, [ 6 ] 지점에서 10 방향으로 보내는 경우와 5 방향으로 보내는 경우는 [ 5 ] 지점에서 6으로 보내는 경우와 [ 6 ] 지점에서 10 방향으로 보내는 경우와 동일하므로 아래 그림과 같은 방법으로 모든 경우에 대해서 Weak 배열을 만들어 볼 수 있다.

● 그 후, 백트레킹을 이용해서 어떤 친구부터 배치할지 가능한 모든 경우에 대해서 현재 Weak 배열에서 탐색을 진행해보면 된다.

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

int ans = 9999;

void playGame(deque<int> dq, vector<int> weak, vector<int> dist) {
	int p = 0, c = 0;
	bool check[15] = {};
	for (int j = 0; j < dist.size(); j++) {
		int l = p;
		while (l < weak.size() && dq[l] - dq[p] <= dist[j])
			check[l++] = 1;
		c++; // 친구 추가!
		p = l;
		if (p >= weak.size())
			break;
	}

	for (int j = 0; j < weak.size(); j++)
		if (check[j] == false) return;
	ans = min(ans, c);
	return;
}

void bt(deque<int> dq, vector<int> weak, vector<int> dist, vector<int> temp, bool visited[8], int size) {
	if (temp.size() == size) {
		playGame(dq, weak, temp);
		return;
	}
	for(int i = 0; i < size; i++)
		if (visited[i] == false) {
			visited[i] = true;
			temp.push_back(dist[i]);
			bt(dq, weak, dist, temp, visited, size);
			temp.pop_back();
			visited[i] = false;
		}
	return;
}

int solution(int n, vector<int> weak, vector<int> dist) {
	ans = 9999;
	deque<int> dq;
	for (int i = 0; i < weak.size();  i++)
		dq.push_back(weak[i]);

	for (int i = 0; i < weak.size(); i++) {
		// 백트레킹으로 가능한 모든 dist 순서마다 진행을 해보자.
		bool visit[8] = {};
		vector<int> temp;
		bt(dq, weak, dist, temp, visit, dist.size());

		// dq 배열 하나씩 shift
		dq.push_back(dq.front() + n);
		dq.pop_front();
	}
    
	if (ans == 9999) return -1;
	return ans;
}

---