[백준 C++] 15649 N과 M (1) - 백트래킹

15649번: N과 M (1)

#include <iostream>
using namespace std;

int N, M;
bool Visit[8];
int Seq[8];

void Print()
{
	for (int i = 0; i < M; ++i)
	{
		cout << Seq[i] + 1 << ' ';
	}
	cout << '\n';
}

void DFS(int CurIdx)
{
	if (CurIdx == M)
	{
		Print();
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		if (Visit[i])
		{
			continue;
		}

		Seq[CurIdx] = i;
		Visit[i] = true;
		DFS(CurIdx + 1);
		Visit[i] = false;
	}
}

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

	cin >> N >> M;

	DFS(0);
}

---

 

DFS & 백트래킹 문제입니다.

중복없이 M개를 고른 수열을 출력해야하기 때문에

방문 체크 배열을 따로 관리하면서 각 경우를 탐색하도록 했습니다.