득이공간

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

PS/알고리즘 문제풀이

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

쟁득 2024. 3. 4. 16:02
 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

#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개를 고른 수열을 출력해야하기 때문에

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