15649번-N과 M (1)

중요 지식

---

백트래킹

코드

---

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int v[9] = {0};
int arr[9] = {1};

void func(int k){
    if(k == M){
        for(int i = 0; i < M; i++){
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }

    for(int i = 1; i <= N; i++){
        if(!v[i]){
            arr[k] = i;
            v[i] = 1;
            func(k+1);
            v[i] = 0;
        }
    }
}

int main(){
    cin >> N >> M;

    func(0);
  
    return 0;
}

풀이

---

func(int k) 설명

0. arr[]의 각 자리마다 1~N까지 조회한다

1. arr[k]에 1~N중 사용하지 않은 수를 넣고 v[]에 체크한다

2. arr[k]의 뒷 자리로가서 또 1~N중 사용하지 않은 수를 한다 재귀: func(k+1);  

3. arr[]을 모두 채웠다면 수열을 출력하고 리턴한다

 

8중 for문을 돌려 코드가 산처럼 될 수 있었지만 재귀로 간략화해서 가독성을 잡을 수 있습니다.