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

백준 단계별로 풀어보기 [백트래킹] N과 M (1)

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

15649번: N과 M (1)

 

[풀이]

dfs 완전 탐색 기법을 이용해서 풀 수 있는 백트래킹 문제이다. 1~n 까지의 자연수 중에서 길이가 m인 수열을 모두 구해 출력해야 하는데, visited[] bool 배열을 선언해 방문했는지 여부를 체크하고 방문하지 않았으면 list 배열에 해당 숫자를 저장한다. count가 m과 같아지면 m 길이의 수열을 만족하는 것이므로 출력을 해준다. 재귀를 이용한 dfs를 구현해 풀 수 있었다.

 

[코드]

#include <iostream>
#include <algorithm>
#define MAX 9

int n, m;
bool visited[MAX] = { false, };
int list[MAX];

void dfs(int count) {
	if (count == m) {
		for (int i = 0; i < m; i++) {
			std::cout << list[i] << " ";
		}
		std::cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			list[count] = i;
			dfs(count+1);
			visited[i] = false;
		}
	}

}

int main() {
	std::cin >> n >> m;
	dfs(0);

	return 0;
}