[백준 C++] 15654 N과 M (5) - 백트래킹

15654번: N과 M (5)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

int N, M;
vector<int> Numbers;

void DFS(int Sequence[], int Index, bool Visited[])
{
	if (Index == M)
	{
		for (int i = 0; i < M; ++i)
		{
			cout << Sequence[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		if (!Visited[i])
		{
			bool NewVisited[8];
			memcpy(NewVisited, Visited, sizeof(bool) * 8);
			NewVisited[i] = true;
			Sequence[Index] = Numbers[i];
			DFS(Sequence, Index + 1, NewVisited);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	Numbers.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		int Number;
		cin >> Number;
		Numbers.emplace_back(Number);
	}

	sort(Numbers.begin(), Numbers.end());

	int Sequence[8];
	bool Visited[8] = { false };
	DFS(Sequence, 0, Visited);
}

---

 

깊이 우선 탐색 & 백트래킹을 이용해서 푸는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 입력 받은 숫자 배열 오름차순 정렬

2. 빈 컨테이너, 방문 체크 배열 생성 및 초기화

3. DFS 탐색 - 미방문 숫자는 컨테이너에 담고 방문 체크 및 재귀 함수 호출

4. M만큼 숫자가 담긴 컨테이너는 출력