(백준/C++) 15649_N과 M(1)

백준 15649번: N과 M은 백트래킹을 시작하기 좋은 연습문제라고 생각됩니다.

이번 문제에서는 값을 순회하고 각 수에 대한 방문 여부를 체크하는 것으로 배열과 재귀 함수를 통해 구현해봤습니다.

이때, 각 수에 대한 방문 여부를 판단하는 것이 백트래킹의 역할입니다.

즉, DFS로 모든 경우의 수를 찾아가면서, 백트래킹을 통해 이미 선택된 숫자를 선택하지 않는 방법으로 풀어내는 백트래킹 문제입니다.

깊이 우선 탐색(DFS)은 트리나 그래프 등의 자료구조를 탐색하는 알고리즘 중 하나로, 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식입니다.
스택을 사용하거나 재귀 호출을 통해 구현할 수 있습니다.

백트래킹은 가능한 모든 상태를 탐색하는 알고리즘입니다.
해결책으로 이어질 것 같지 않은 상태를 발견하면 그 상태의 상위 상태로 돌아갑니다 (즉, “뒤로 돌아갑니다”). 이는 불필요한 상태를 탐색하지 않으므로 시간을 절약할 수 있습니다.

접근법 (hint)

우선, 백트래킹을 이해하기 위한 문제인만큼 접근법을 차근차근 적어보겠습니다.

1. DFS(깊이 우선 탐색) 및 백트래킹 시작

가능한 수열을 찾아가기 위해 1부터 N까지의 숫자에 대해 M개의 숫자를 선택하는 DFS를 시작합니다.

이때, 저는 DFS는 재귀 함수로 구현했으며, 각 단계에서 선택한 숫자를 표시한 후에 재귀 호출을 했습니다.

2. 숫자 선택 및 백트래킹

해당 숫자가 이미 선택되어 있다면, 바로 다음 숫자를 탐색합니다. 저는 이 부분을 백트래킹이라고 생각합니다.

그리고 기저 사례로써 길이 M을 만족했다면 지금까지의 수열을 출력하고 이전 단계로 돌아가 백트래킹을 계속 합니다. 이때, 이전 단계에서 선택한 숫자의 표시를 지워야 합니다.

---

풀이

저는 방문 여부를 nums 배열을 통해 관리하고, 현재까지 방문한 데이터는 deque로 관리했습니다.

#include <iostream>
#include <queue>
using namespace std;
bool nums[8] = {false,};
deque<int> result;
void visit(int n, int m, int depth) //DFS 시
{
	if(depth == m) //길이 M을 만족했다면 출력
	{
		for (int r : result) cout << r << ' ';
		cout << '\n';
		return;
	}

	for(int i = 0; i < n; i++) //1부터 N까지의 숫자에 대해
	{
		if (!nums[i]) //백트래킹-선택하지 않은 숫자만
		{
			nums[i] = true;
			result.push_back(i + 1);

			visit(n, m, depth + 1); //다음 단계 진행

			nums[i] = false;
			result.pop_back();
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	visit(N, M, 0);
}