순열, 조합 알고리즘 (DFS-Backtracking)

c++에는 algorithm 헤더에 순열을 구하는 next_permutation() 함수가 존재한다.

문제에 순열이나 조합이 나오면 이 함수로 쉽게 구할 수 있는데, 문제는 이 함수는 시간복잡도가 커서 N값이 커지면 시간 초과가 나는 것이다.

BackTracking

그래서 순열, 조합을 다른 방식으로 푸는 방법을 찾았는데, 바로 백트래킹을 사용하는 것이다.

💡 백트래킹은 어떤 노드의 유망성, 즉 해가 될만한지 판단하고, 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가 다음 자식 노드로 가는 방식이다.

순열 구하기

Backtracking과 visit 배열을 사용하여 구현할 수 있다. (코드에 설명 첨부)

#include <stdio.h>
#include <iostream>
#include <vector>

#define MAX 5 // 1부터 5까지 수의 순열을 구한다.

using namespace std;

//vector<int> arr;
vector<int> result;
int visit[MAX]; // (!) 방문 여부를 저장하는 배열

void print_permutation() { // 순열 출력
    for (int i = 0; i < result.size(); i++) {
        cout << result.at(i) << " ";
    }
    cout << endl;
}

void permutation_DFS(int count) { // count개의 수를 이용해 순열을 만든다.
    if (count == 3) {
        print_permutation();
        return;
    }
    
    for (int i = 1; i <= MAX; i++) {
        if (visit[i] == true) // 이미 사용한 숫자라면 다음으로 넘긴다.
            continue;
        
        // (!) Back Tracking 사용
        visit[i] = true; // 방문했다는 표시를 남기고
        result.push_back(i); // result 벡터에 현재 값을 넣어준다.
        
        permutation_DFS(count + 1); // DFS를 사용하여 한 칸 더 내려간다.
        
        result.pop_back(); // Back Tracking
        visit[i] = false; // i에서 빠져나왔기때문에 visit[i]를 false로 바꿔준다.
    }
}

int main() {
    permutation_DFS(0);
    
    return 0;
}

조합 구하기

순열 코드와 차이점은 print부분과 result 벡터를 사용하지 않는다는 점이다. (코드에 설명 첨부)

#include <stdio.h>
#include <iostream>
#include <vector>

#define MAX 5 // 1부터 5까지 수의 순열을 구한다.

using namespace std;

//vector<int> arr;
int visit[MAX]; // (!) 방문 여부를 저장하는 배열

void print_combination() {
    for (int i = 1; i <= MAX; i++) {
        if (visit[i] == true) // 조합과 순열의 차이 (조합은 중복 제거)
            cout << i << " ";
    }
    cout << endl;
}

void combination_DFS(int index, int count) { // count개의 수를 이용해 순열을 만든다.
    if (count == 3) {
        print_combination();
        return;
    }
    
    for (int i = index; i <= MAX; i++) {
        if (visit[i] == true) // 이미 방문한 곳이라면 건너뛴다.
            continue;
        
        visit[i] = true; // 방문 표시를 남긴다.
        combination_DFS(i, count + 1);
        visit[i] = false; // 체크 취소 (다른 자식 노드를 체크하기 위해)
    }
}

int main() {
    combination_DFS(1, 0);
    
    return 0;
}

 

[참고]

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

DFS, BFS, 백트래킹(Backtracking)

[바킹독의 실전 알고리즘] 0x0C강 - 백트래킹

순열, 조합 알고리즘 - DFS로 구하기(백트래킹), C++, Python