c++/ 자료구조&알고리즘 개념 복습하기 - 14 / 백트래킹, 조합, STL next_permutation

백트래킹??

• 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
• 모든 경우의 수를 확인해야 할 때 사용
  -> for 로는 확인 불가한 경우(깊이가 달라질때)
• 더 이상 볼 필요 없는 부분은 쳐내는게 핵심
• 재귀 활용

---

< 예제 >

https://www.acmicpc.net/problem/15649

int n,m;
int arr[10];
bool isused[10];

void func(int k){ // 현재 k개까지 수를 택했음.
  if(k == m){ // m개를 모두 택했으면
    for(int i = 0; i < m; i++)
      cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
    cout << '\n';
    return;
  }

  for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
    if(!isused[i]){ // 아직 i가 사용되지 않았으면
      arr[k] = i; // k번째 수를 i로 정함
      
      isused[i] = 1; // i를 사용되었다고 표시
      
      func(k+1); // 다음 수를 정하러 한 단계 더 들어감
      
      isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 
      //i를 이제 사용되지않았다고 명시함.
      
      // arr[k]는 어짜피 다른 값으로 덮힐 예정이므로 따로 처리 안해줘도 된다
      
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  func(0);
}

---

https://www.acmicpc.net/problem/9663

• N-Queen 문제
• 행별로 생각
• 특정 지점에 놓았다면, 그 지점의 좌측 하단 대각선, 하단 직선, 우측 하단 대각선 방향은 더 이상 놓을 수 없다는 점을 활용!!

---

https://www.acmicpc.net/problem/1182

• 부분집합의 개념을 활용 가능
• 현재 원소를 선택 or 선택x 의 경우로 나누기!

---

< STL next_permutation - 순열 >

• 헤더에 #include < algorithm > 선언을 통해 사용 가능

• 순열과 조합에서 매우 유용

• 현재의 수열을 사전 순으로 생각했을 때의 다음 수열로 만들고 true를 반환한다!!!
  -> 현재 123 이라면 다음은 132가 된다

• 현재 수열이 사전순으로 생각했을 때 가장 마지막이라면 false를 반환
  
  

• next_permutation 함수는 기본적으로 중복을 제거 하여 반환해준다!!
  
  

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

using namespace std;


int main(void) {
	int a[3] = { 1,2,3 };
	do {
		for (int i = 0; i < 3; i++)
			cout << a[i];
		cout << "\n";
	} while (next_permutation(a, a + 3));
}

/* 출력결과
123
132
213
231
312
321
*/

• 순열 - vector 사용

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> v;
    for(int i = 1; i <= 3; i++) {
        v.push_back(i);
    }

    do {
        for(int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << "\n";
    } while (next_permutation(v.begin(), v.end()));
    // end의 경우 해당 리스트의 마지막 요소의 한칸 뒤 주소를 가리킨다
   
    return 0;
}

---

< 조합 >

• 1 2 3 4 에서 2개를 순서 상관 없이 뽑는 모든 경우
• 0 과 1을 활용!!1

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

using namespace std;


int main(void) {
	int a[4] = { 0, 0, 1, 1 };
	do {
		for (int i = 0; i < 4; i++)
			if (a[i] == 0)
				cout << i + 1;
		cout << "\n";
	} while (next_permutation(a, a + 4));
}


/*출력
12
13
14
23
24
34
*/

• next_permutation은 더 큰 순열을로 재배열을 할 수 있으면 반복하여 구해내는 구조이므로 앞에 이미 큰 원소들이 배치되어 있으면 반복하지 않게 된다
• 정렬 후 사용하자!

---

• next_permutation 참고 링크
• https://twpower.github.io/82-next_permutation-and-prev_permutation
• https://notepad96.tistory.com/entry/C-%EC%88%9C%EC%97%B4Permutation-nextpermutation

---

< 재귀를 통한 조합 >

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

using namespace std;

int N;
int M;
int visited[100] = {0};

void getResult(int toChoose, int num) {
    if (toChoose == 0) // 기저조건 - M개 모두 골랐다
    {
        for(int i = 0; i < N; i++) {
            if (visited[i]) cout << i+1 << " ";
        }
        cout << "\n";
        return;
    }
    else
    {
        for(int i = num; i < N; i++) { 
            visited[i] = 1;
            getResult(toChoose - 1, i + 1); 
            visited[i] = 0;
            
            // 한 개 골랐으므로 toChoose - 1 넘긴다 
            // 방금 선택한 index 이후 부터 고려하기 위해 i+1 넘긴다
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    cin >> M; // N개 중에 M개를 고른다

    getResult(M, 0);

    return 0;
}

// 입력 : 6 3
// 출력 : 
1 2 3 
1 2 4 
1 2 5 
1 2 6 
1 3 4 
1 3 5 
1 3 6 
1 4 5 
1 4 6 
1 5 6 
2 3 4 
2 3 5 
2 3 6 
2 4 5 
2 4 6 
2 5 6 
3 4 5 
3 4 6 
3 5 6 
4 5 6 

---