백준 15650 풀이

링크텍스트

15649 문제에 조건이 추가된 문제이다.

그래서 기존의 소스코드에 조건을 추가하여 작성하는 것을 기본으로 했다.

이번 문제의 핵심은

시작값보다 작은 값을 선택할 수 없다.

는 것이다.
만약 2를 방문했다면 1을 방문할 수 없다.
이 점을 알았다면 빠르게 해결할 수 있다.

dfs 함수에 pos라는 파라미터를 추가했는데 이유는 시작 위치를 정해주기 위해서다.
시작값보다 작은 값을 선택할 수 없다는 것은 시작위치보다 작은 값은 방문할 필요가 없다는 것과 마찬가지이기 때문에 탐색의 시작 위치를 조정해주는 것으로도 답을 구할 수 있었다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;

int n;
int m;
bool visited[9] = { 0, };
int arr[9];

void dfs(int cnt,int pos) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = pos; i <= n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			arr[cnt] = i;
			dfs(cnt + 1,i);
			visited[i] = false;
		}
		
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int answer = 0;

	cin >> n >> m;
	
	dfs(0,1);
	
	return 0;
}