[C++][백준] - N과 M (1) (15649번)

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

15649번: N과 M (1)

🔔 문제 : 

1 <= M <= N <= 8 인 조건으로

 

1부터 N까지 자연수 중에서 중복 없이 길이가 M인 수열을 구하는 문제입니다.

 

 

---

🔔 Kick Point :

재귀적으로 순열을 구하는 방법을 사용을 했습니다.

 

arr[] 배열은 자리수에 맞게 숫자를 담는 역할을 하고

isVisited[] 배열은 1~N까지 숫자가 담겨져 있는지 유무를 확인합니다.

 

1. arr[] 배열에 자리수 별로 숫자를 담아줍니다.

예를들어 N = 5, M = 3 에서 "123" 숫자라면  

arr[0] = 1, arr[1] = 2, arr[2] = 3 이렇게 담겨 있습니다.

 

2. dfs 함수 안 for 루프를 통하여 자리수별로 모든 숫자를 넣어줍니다.

dfs() 함수 속 cnt가 자리수를 의미합니다.

 

---

🔔 Code :

#include <iostream>
using namespace std;

// 1. recursive 

int arr[8] = {0,};
bool isVisited[8] = { false, };

void dfs(int n, int m, int cnt = 0) {
	
	if (cnt == m) {
		for (int i = 0; i < m; i++) { cout << arr[i] << " "; }
		cout << "\n";
		return;
	}

	for (int i = 0; i < n; i++) {
		
		if (isVisited[i]) { continue; }

		arr[cnt] = i + 1;
		isVisited[i] = true;
		
		dfs(n, m, cnt+1);
		isVisited[i] = false;
	}
	

}

int main() {

	int n, m;
	cin >> n >> m;
	dfs(n, m);

}

---