[백준 15651] 완전탐색_브루스포스(Brute Force)

 안녕하세요. 오늘은 알고리즘 중에서 완전탐색 브루스포스에 대해서 포스팅하겠습니다! 

 

 완전탐색은 문제를 해결하기 위해 확인해야하는 모든 경우를 전부 탐색하는 방법입니다. 예를 들어, 4가지 숫자로 이뤄진 금고의 비밀번호를 알고자한다면 0000부터 9999까지 모든 경우의 수를 직접 시도해보는 방법이 브루스 포스 알고리즘입니다.

 

 브루스포스 알고리즘 유형은 보통 다음과 같습니다.

 N개중 (중복을 허용해서/중복없이) M개를 (순서 있게 나열하기/순서 상관없이 고르기)

 

15651번은 브루스포스 유형 중 N개중 중복을 허용해서 M개를 순서있게 나열하는 방법입니다.

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

15651번: N과 M (3)

---

 브루스포스는 가능한 모든 경우를 탐색하는 방법입니다. 이번 구현에서는 함수를 이용해서 직관적으로 코드를 구현해보겠습니다. 이 코드에서 이해해야할 부분은 총 세가지입니다. 1. input 함수, 2. selected 배열, 3. rec_func 함수

 

 먼저, input() 함수는 N(나타낼 숫자의 범위)과 M(나타낼 숫자의 개수)를 받아옵니다.

 

 두번째로, selected 배열은 숫자의 조합을 배열에 넣었다가 다시 출력하도록 도와줍니다. 

 rec_func(k) 함수는 selected 배열을 이용해서 k번째 자리에 들어올 수를 모두 찾는 함수입니다. 이해를 돕기 위해 그림을 첨부하겠습니다.

 마지막으로 rec_func() 함수는 selected 배열의 알맞은 인덱스에 알맞은 값을 넣고 제때에 출력할 수 있도록 하는 함수입니다.

void rec_func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++)
		 	cout << selected[i] << " ";
		cout << "\n";
		return;
	}
	for (int cand = 1; cand <= N; cand++) {
		selected[k] = cand;
        cout<< "k: "<< k<< " selected : "<< selected[k] <<" ";
		rec_func(k + 1);
		selected[k] = 0;
        cout<<"\n";
	}
}

 rec_func() 함수는 재귀함수입니다. 따라서 함수의 인풋값을 잘 보시고 어떤 방식으로 동작하는지에 집중하셔야합니다. rec_func() 함수는 인풋값인 k가 배열의 끝까지 갈 경우(k==M+1) 해당 배열을 출력합니다. 인풋값 k가 M+1이 되기 전까지 selected 배열에 출력할 경우의 수를 입력합니다. 그리고 입력하는 과정은 재귀로 이뤄집니다. 

 rec_func함수가 재귀되는 과정을 그림으로 나타냈습니다. 참고로 k=1 일때 1,2 뿐만 아니라 3까지 보라색 형광펜이 칠해진 부분에 나와야했지만 그냥 생략했습니다. k가 1일때 k가 2인 경우(rec_func(2))를 부르고, k가 2인 경우에도 k가 3인 경우(rec_func(3))를 부릅니다. 이때 k=3일 경우 k==M+1이므로 앞에서 selected 배열에 k==1일때, k==2일때 넣었던 숫자들을 출력합니다.

---

 완성 코드입니다.

#include <iostream>
using namespace std;

int N, M, selected[10];
void input() {
	cin >> N >> M;
}

void rec_func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++)
			cout << selected[i] << " ";
		cout << "\n";
		return;
	}
	for (int cand = 1; cand <= N; cand++) {
		selected[k] = cand;
		rec_func(k + 1);
		selected[k] = 0;
	}
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	input();
	rec_func(1);
	return 0;
}