백준 15649 N과 M (1)

문제 링크: https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

순열 (permutation)을 출력하는 문제이다.

예를 들어 n = 3, m = 2인 경우에서

1 2, 1 3, 2 1, 2 3, 3 1, 3 2와 같이 총 3P2 = 6가지 경우를 출력해야 하는 문제이다.

 

재귀함수 solve 내부를 보면, idx가 m이 될때 출력해줘야 하고, m이 되기 전에는 a 배열에 어떤 숫자들이 어떻게 들어가는지를 결정해야 한다. 숫자를 1부터 n까지 for문을 돌면서 사용되지 않은 숫자를 a 배열의 idx번째 칸에 넣어주고, 숫자를 사용했다고 표시해준다. 그런다음 재귀함수를 호출해주고, 방금 사용했던 숫자를 다시 사용하지 않았다고 표시해준다. 이부분이 백트래킹이다.

예를 들어 n = 4, m = 3 인 경우에서

1 2 3

1 2 4

이미 1, 2, 3, 4 주어진 4개의 숫자를 다 사용했기 때문에 백트래킹 부분의 코드(아래 코드의 20번째 줄)를 빼면 다음에 나와야 할 1 3 2가 나오지 않고 종료된다. 

#include <bits/stdc++.h>
using namespace std;
 
int n, m, a[10];
bool used[10];
 
void solve(int idx) {
    if(idx == m) {
        for(int i = 0; i < m; i++)
            cout << a[i] << ' ';
        cout << '\n';
        return;
    }
 
    for(int i = 1; i <= n; i++) {
        if(!used[i]) {
            used[i] = true;
            a[idx] = i;
            solve(idx + 1);
            used[i] = false;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    solve(0);
    return 0;
}