[Algorithm: 백트래킹(Backtracking)] BOJ 15649 : N과 M(1) (C++)

백트래킹이란?

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아가는 기법!

 

기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다'(완전 탐색 기법) 아이디어를 중심으로 한다. 백트래킹은 완전 탐색 기법 중 하나인 DFS에서 가지치기(Pruning)을 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 탐색 기법이다.

 

BOJ 15649 N과 M(1)  

이 문제는 1부터 N가지의 숫자 중 M개를 순서 있게 뽑기와 유사하다. 

순열의 특징은 중복된 원소가 있으면 안된다는 것이다. 그러면 만일 중복된 원소를  만나는 순간 다른 경로로 가면 된다.

 

참고한 사이트이다.

https://yabmoons.tistory.com/100

[ 순열과 조합 구현 ] - 재귀를 통한 구현(2 - 순열) (C++)

정답 코드

#include <iostream>
#include <vector>

#define MAX 8
using namespace std;
/*
 * 문제 : 자연수의 크기 MAX : M , 수열의 길이: N
 * 중복 없이! 중복이 있는 것을 제외해야함 !  중복이 있는 것을 체크해야함.
 *
 */
bool visited[MAX + 1] = {false,};
int N, M;
vector<int> v;
void dfs(int cnt) {
    if (cnt == M) {
        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << "\n";
    }
    for (int i = 1; i <= N; i++) {
        if(visited[i] != true){
            visited[i] = true;
            v.push_back(i);
            dfs(cnt + 1);
            v.pop_back();
            visited[i] = false;
        }
    }
}

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

어려웠던 부분

- 길이를 맞추는 부분이 쉽지 않았다. 

=> 초기에는 cnt를 전역변수로 선언하고 cnt를 늘려주는 방식으로 길이 체크를 했는데 runtime에러가 나고 출력이 안돼서 다른 방식으로 cnt를 사용하지 않는 방식으로 바꿔보았다. 변수는 필요 없지만 함수안에서 지금 길이를 체크할 수 있게끔 바꿔주었다.