[Silver 2] 15663번 N과 M (9)

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

15663번: N과 M (9)

 

이 문제는 벡트래킹을 통해 해결할 수 있다.

 

알고리즘은 다음과 같다.

• 입력 배열의 요소를 정렬한다. (오름차순 출력을 위해)
• dfs를 0번 요소부터 수행한다.
• 만약 M번째 자리까지 탐색했다면 출력한다.
• 0번째 요소부터 N번째 요소까지 반복을 진행한다.
  • 이때 방문하지 않았으며, i번째 배열의 요소가 중복된 값이 아니라면
  • 출력을 위한 배열에 값을 삽입하고, 중복 값 검사를 위한 변수에 i번째 요소를 넣는다.
  • 방문 표시를하고 다음 자리를 탐색한다.
  • 탐색이 끝나면 방문하지 않았다고 값을 초기화한다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, arr[9], result[9]; 
int visited[9] = { 0, };

void dfs(int cnt) {
	if (cnt == M) {
		for (int i = 0; i < M; i++)
			printf("%d ", result[i]);
		printf("\n");
		return;
	}
	int num = 0;
	for (int i = 0; i < N; i++) {
		if (!visited[i] && arr[i] != num) {
			result[cnt] = arr[i];
			num = result[cnt];
			visited[i] = 1;
			dfs(cnt + 1);
			visited[i] = 0;
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	sort(arr, arr + N);
	dfs(0);
}