[백준/c++] 15649 N과 M(1)

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

전형적인 백트래킹 문제,, DFS를 참고해서 풀면 된다.

중복도 허용하기 때문에 백트래킹계의 순열이라고 볼 수 있다. 

 

DFS의 재귀를 이용하여 풀었다.

 

자세한 설명은 코드에 적어놓았다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool checked[9] = { false, };
int arr[9] = {};
int a, b;

void dfs(int depth) {
	//만약 dfs의 depth가 b와 같으면 arr배열에 담긴 순열 출력, 종료
	if (depth == b) {
		for (int i = 0; i < b; i++) {
			cout << arr[i] << " ";
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= a; i++) {
		if (!checked[i]) {
			//만약 i가 아직 방문되지 않은 숫자라면 방문 체크하기
			checked[i] = true;
			//방문체크 한 뒤, 현재 dfs 깊이에 기록된 arr 갱신
			arr[depth] = i;
			//재귀 사용해서 반복, 더 깊이 들어감
			dfs(depth + 1);
			//depth번째 수를 i로 정한 모든 경우에 대해 확인했기 때문에 사용되지 않았다고 표시함 (백트래킹 설정)
			checked[i] = false;
		}
	}
}

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

	dfs(0);		// 백트래킹 0부터 시작
}

백트래킹에 대해 모른다면 절대 혼자 할 수 없을듯..어케 알았냐고요? 저도 그랬기 때문..