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

문제

코드

#include <iostream>
using namespace std;

int N, M;
int arr[10]; // 수열을 저장하는 배열
bool isused[10]; // 이미 사용한 숫자인지 체크하는 배열

void func(int k) {
    
    // 수열의 길이가 M과 같으면 출력
    if(k == M) {
        for(int i=0; i<M; i++){
            cout << arr[i] << ' ';
        }
        cout << '\n';
        return;
    }
    
    // 백트래킹
    for(int i = 1; i<=N; i++){
        if(!isused[i]){
            arr[k] = i;
            isused[i] = 1; // 사용됐음을 표시
            func(k+1); // 출력 후 여기로 리턴
            
            isused[i]=0; // 새 수열이 시작될 때 전에 자리에 있던 것은 0으로 처리 됨
        }
    }
}

int main() {
    cin >> N >> M;
    
    func(0);
}

풀이

• arr 배열: 수열 저장(0부터 시작)
• isused 배열: 사용한 수인지 체크하는 배열
• k: 현재 탐색하고 있는 수열의 위치(ex. arr[0], arr[1])

N=4, M=2 인 경우
K=0 일 때 1 을 고정한 후 재귀적으로
k=1 -> 2
k=2 -> 출력 1 2

다시 k=1 로 돌아가 (이때 isused[ i(=2) ] = 0으로 초기화)
k=1 -> 3
k=2 -> 1 3 출력

다시 k=1 로 돌아가
k=1 -> 4
k=2 -> 1 4 출력

그리고 isused[4], isused[1]을 초기화한다.

다시 k=0이 되어 2를 고정한 후
k=1 -> 1
k=2 -> 2 1 출력

이 과정을 반복한다.

후기

백트래킹 부분을 이해하는데 오랜 시간이 걸렸다.
재귀를 공부하고 풀었으면 더 수월했을 것 같다.
바킹독님 영상으로 공부했다.