DFS를 활용한 조합

 조합이란 우리가 고등학교 때 배웠던 Combination을 말한다. 

조합은 순서를 반영하지 않는다. 즉 1 2 3 과 2 1 3 은 같은 조합이다. 우리가 아이폰, 에어팟 조합과 에어팟, 아이폰 조합을 구분하지 않는 것과 같다.

 

개발을 하다보면 조합을 활용해야할 경우가 상당히 많다. 그때 dfs를 활용한 조합 코드를 유용하게 사용할 수 있다. 

그러나 완전탐색을 해야하는 경우나 N이 크다면 조합은 지양하는 것이 좋은데, 우선 백트레킹 방식을 사용하는 dfs 조합은 재귀 방식을 사용하기 때문에 자연스럽게 오버헤드의 부담이 생길 수 밖에 없다.

 

EX)

1, 2, 3, 4 중 3개를 뽑는다고 가정하자.

그렇다면 

1 2 3

1 2 4

1 3 4

2 3 4 

 

앞자리수를 고정하는게 가장 편리하다 . dfs또한 이를 따른다.

코드를 짜기 전 생각해보자 어떻게 해야할까?

1. 각 자리수를 고정하고, 이 숫자를 현재 조합에 포함하고 있는지 확인해야한다.

2. 조합이기 때문에 첫번째 자리수가 다시나올 필요가 없다. => 그저 앞으로만 나가면 된다.

3. 원하는 원소의 갯수가 채워지면 마지막에 들어온 원소를 제거하고 다른것을 넣는다 => 백트래킹

 

그럼 코드는 이렇게 된다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> Array;

bool check[4] = { false, };

void Combination(int idx, int cnt, int max) {
	if (cnt == max) {
		for (int i = 0; i < 4; i++) {
			if (check[i] == true)
				cout << Array[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = idx; i < 4; i++) {
		if (check[i] == true) 
			continue;
		check[i] = true;
		Combination(i, cnt + 1, max);
		check[i] = false;
	}
}


int main() {
	Array.push_back(1);
	Array.push_back(2);
	Array.push_back(3);
	Array.push_back(4);

	Combination(0,0, 3);
}

이번엔 코드 순으로 살펴보자. 

 

처음 함수가 실행됐을 때 상태는

한개도 선택되어있지 않으므로 idx = 0, cnt = 0 이다. 

그럼 먼저 0번째 원소를 선택하고 0번째는 선택 되었다고 체크한다.

현재 조합 : 1

 

그 다음 Conbination(1,1) 이 들어간다. 

이번에는 한개가 선택되어있다.

idx = 1 이므로 1번째 원소를 선택한다. 이제 1번째 원소가 체크 되었고 두개를 골랐다.

현재 조합 : 1, 2

 

그 다음 Combination(2,2)

이번에는 두개가 선택되어있다.

idx = 2 이므로 2번째 원소를 선택한다. 이제 2번째 원소가 체크 되었고 세개를 골랐다.

현재 조합 1, 2, 3

 

Combination(3, 3)

앗! 3번째 원소를 선택하려 했는데 3개가 모두 선택되었다.(0번부터 샜음을 잊지말자) 그러므로 출력을 한 번 해준다. return이 있기 때문에 이제 Combination(2,2)가 끝난 경우로 갈 것이다. 

2번째로 골랐던 3의 선택을 취소한다 <===== 백트레킹!!

이제 2개가 골라져 있고, 다음 반복을 한다.

 

Combination(4, 3)

 백트레킹을 했기 때문에 골라져 있는 원소는 3개를 골랐고 2,2 에서의 다음 반복으로 1,2,4 가 골라져있다.

 

.

.

.

 

이런식으로 반복되며 1가지 길(한가지를 고정하고) 끝까지 파고드는 것은 dfs의 전형적인 성질이다.