백 트래킹(Back tracking)

Silver 15652

첫시도

#include <iostream>
using namespace std;

int N, M;
int arr[9];
bool visited[9];

void dfs(int k) {
	if (k == M) {
		for (int i = 0; i < M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	else {
		for (int i = 1; i <= N; i++) {
			if ((arr[k-1]<=i||arr[0]==0)) {
				arr[k] = i;
				dfs(k + 1);
			}
		}
	}
}

int main() {
	cin >> N >> M;
	dfs(0);


	return 0;
}

if문 안에 조건식을 넣어봤다.
1. 비내림차순이므로 중복 가능하고 다음수가 전 수보다 커야함
arr[k] = i가 오기 전에 arr[k-1] <= i여야 한다
2. arr[0]==0 시작점 잡아주기

두번째시도

#include <iostream>
using namespace std;

int N, M;
int arr[9];
bool visited[9];

void dfs(int x,int k) {
	if (k == M) {
		for (int i = 0; i < M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	else {
		for (int i = x; i <= N; i++) {
			
				arr[k] = i;
				dfs(i , k + 1);
			
		}
	}
}

int main() {
	cin >> N >> M;
	dfs(1,0);


	return 0;
}

첫 시도보다 더 간결한 코드가 있었다.
1. dfs함수 매개변수에 int x 를 추가하여 수열 다음 원소의 값의 시작점을 가리키며 for문 안에 있기 때문에 1씩 커지며 함수를 실행한다.

Silver 15650

좋은 풀이

#include <iostream>
using namespace std;

int N, M;
int arr[9];
bool visited[9];

void dfs(int x, int k) {
	if (k == M) {
		for (int i = 0; i < M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	else {
		for (int i = x; i <= N; i++) {
			arr[k] = i;
			dfs(i + 1, k + 1);
		}
	}
}

int main() {
	cin >> N >> M;
	dfs(1, 0);


	return 0;
}

1. 매개변수에 int x를 추가한다.
2. 두번째 for문의 시작점을 x로 잡고 int i=x 선언후 다음 함수를 dfs(i+1, k+1)을 호출 해주면 x+1부터 +1씩 되는 수열을 가질 수 있으므로
   문제에서 요구하는 중복이 안되고 이전수보다 큰 수열을 만들 수 있다.

Silver 15663

첫시도

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

int arr[9];
bool visited[9];
int result[9];
int N, M;
int dif[9];
int cnt;
void dfs(int k) {
	if (k == M) {
		for (int i = 0; i < M; i++) {
			if (dif[i] == result[i]) { cnt++; }
		}
		if (cnt == M) { cnt = 0; return; }
		else {
			for (int i = 0; i < M; i++) {
				cout << result[i] << ' ';
				dif[i]=result[i];
				cnt = 0;
			}
			cout << '\n';
			return;
		}
		
	}
	else {
		for (int i = 0; i < N;i++) {
			if (visited[i] == false) {
				visited[i] = true;
				result[k] = arr[i];
				dfs(k + 1);
				visited[i] = false;
			}
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
	dfs(0);
	return 0;
}

중복 되는 수열을 출력하지 말아라해서 단순히 결과 출력 전에 바로 직전에 출력한 결과와 같은지 다른지 판별하여 출력하는 프로그램을 작성하였지만 반례가 생긴다

입력
4 2
9 7 9 1

출력
1 7
1 9
7 1
7 9
9 1
9 7
9 9
9 1
9 7
9 9

위와 같이 8번 째 줄은 출력이 되면 안되는데 바로 직전 출력물과 같은지 다른지 비교하므로 먼저 출력 된 9 1, 9 7, 9 9를 걸러내지 못한다.
그래서 다시 출력되는 순서를 그려보았다

1 7 O
1 9 O
1 9 X
7 1 O
7 9 O
7 9 X
9 1 O
9 7 O
9 9 O
9 1 X
9 7 X
9 9 X