백준/15649/백트래킹/N과 M(1)

백준/15649/백트래킹/N과 M(1)
백트래킹에 가장 기본 개념인 순열을 이용하는 문제로

void func(int k) {
	if (k == M) {
		for (int i = 0; i < k; i++) {
			if (i == k - 1)
				cout << arr[i];
			else
				cout << arr[i]<<" ";
		}
		cout << endl;
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (!isused[i]) {
			arr[k] = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
...

문제는 1부터 N라는 수에서 M번을 뽑아 만들 수 있는 순열을 출력하는 것을 원하므로
k라는 순열의 순서를 정의하고 이 M번을 뽑았을 경우 출력하게 조건을 걸어둔 뒤
아래에서 for문을 통해 arr에 배열을 채워가면 된다.

	for (int i = 1; i <= N; i++) {
		if (!isused[i]) {
			arr[k] = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
    ...

이 for문의 원리는 우선 순열의 첫번째 요소를 뽑고 그 첫번째 요소에 isused라는 lock을 걸어놔 사용하지 못하게 하고 다음 순열을의 n번째 요소를 뽑기 위해 재귀를 하는 원리이다.
그러면 다음으로 들어간 함수에서 isused가 된 함수는 해당 요소로 사용하지 못하기 때문에 for문을 돌게 된다.
끝까지 갔을 경우 만든 순열을 뽑아내고 재귀하면 해당 isused는 false로 바꿔줘도 다음 for문이 돌기 때문에 해당 요소가 다시 쓰일일은 없다.

cout<<endl;
cout<<'\n';

첫번째 풀이에 경우 각 순열을 구분하기 위해 cout<<endl을 했는데 endl은 버퍼의 flush를 해서 스트림에 요소가 남아있는지를 확인하기 때문에 느려 시간 초과가 발생하였다.

그래서 두번째 풀이에 '\n'을 대신사용하여 시간초과를 방지하고 문제를 풀었다.

풀이

1. 첫번째 풀이

#include<iostream>
using namespace std;

int arr[10];
bool isused[10];
int N, M;

void func(int k) {
	if (k == M) {
		for (int i = 0; i < k; i++) {
			if (i == k - 1)
				cout << arr[i];
			else
				cout << arr[i]<<" ";
		}
		cout << endl;
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (!isused[i]) {
			arr[k] = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	func(0);
}

2. 두번째 풀이

#include<iostream>
using namespace std;

int arr[10];
bool isused[10];
int N, M;

void func(int k) {
	if (k == M) {
		for (int i = 0; i < k; i++) {
			if (i == k - 1)
				cout << arr[i];
			else
				cout << arr[i]<<" ";
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (!isused[i]) {
			arr[k] = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	func(0);
}

3.세번째 풀이(모듈화)

#include<iostream>
using namespace std;

int N, M;
int result[10];
bool used[10];


void func(int);
void solution();

void func(int cur) {
	if (cur == M) {
		solution();
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (!used[i]) {
			result[cur] = i;
			used[i] = true;
			func(cur + 1);
			used[i] = false;
		}
	}
}

void solution() {
	for (int i = 0; i < M; i++)
		cout << result[i] << " ";
	cout << "\n";
}


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	func(0);
}