백트래킹

백트래킹

현재 상태에서 가능한 모든 선택지를 실행해보며 탐색하는 알고리즘

문제 분석

• 1부터 N까지의 숫자 중 중복 없이 사전 순으로 M개 뽑기
• 사전 순 : 앞 숫자가 작을수록 먼저 오고, 앞 숫자가 같다면 두 번째 숫자를 비교해서 정렬하는 방식 ex. (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)

구현

비어 있는 리스트에서 시작해 수를 하나씩 추가하면서 길이가 M인 수열이 완성되면 출력하는 방식으로 구현할 수 있다. 여기서 별은 현재의 리스트 상태를 나타내고 N=4, M=3이다.

1. 함수의 정의 : k번째 자리에 들어갈 숫자를 고르는 함수

void solve(int k)

2. base condition 설정 : 해당 수열의 길이가 M일 때 출력하고 종료

    if (k == M) { 
        for (int i = 0; i < M; i++) cout << arr[i] << " ";
        cout << "\n";
        return;
    }

3. 재귀 식 : 다음 수 고르기

    for (int i = 1; i <= N; i++) {
        if (!isused[i]) {        // i가 아직 수열에 사용되지 않았다면
            arr[k] = i;          // 수열의 k번째 자리에 i를 넣고
            isused[i] = true;    // i를 사용했음을 표시
            solve(k + 1);        // 다음 자리(k+1)를 채우기 위해 재귀 호출
            isused[i] = false;   // 백트래킹: 사용한 i를 다시 사용 가능하게 되돌림
        }
    }
}

코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
int arr[10]; // 수열을 담을 배열
bool isused[10]; // arr[i]의 사용 여부를 T/F로 나타내는 배열

// arr[k]에 들어갈 수를 정하는 함수
void solve(int k) {
	
	// base condition : 리스트 길이가 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; // 사용으로 바꿈

			solve(k + 1);
			isused[i] = 0; // 미사용으로 바꿈
		}
	}

}


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	solve(0);
}

✅ solve(k + 1) 다음에 isused[i] = 0으로 다시 설정하는 이유