[백준] 10974 모든 순열 백트래킹

문제 :

www.acmicpc.net/problem/10974

10974번: 모든 순열

분석 :

사실 전혀 이해가 되지 않아서 블로그들을 참고하여 풀었다. 

dfs가 백트래킹이랑 관련이 깊다 했는데 이 문제가 바로 백트래킹 알고리즘 사용하는 고전적인 문제라고 한다.

c++ 에선 next_permutation이라는 순열 찾는 함수가 <algorithm>에 있다고 한다. 이걸 이용하면 쉽게 풀 수 있을 것 같다.

하지만 백트랙킹 연습을 위해 백트랙킹 방식으로 완전 탐색 문제를 풀어보았다. 

dfs와 마찬가지로 visit (방문했는지 안했는지 검사하는 배열)이 필요로 된다.

v vector에 넣어주는데 방문하지 않았으면 넣어주고 재귀함수를 이용해 방문이 끝나면 다음 차례 방문을 위해 마지막에 넣은 원소를 꺼내준다. 그리고 visit 배열도 false로 만들어 놓는다. 이렇게 반복이 끝나고 순열 input 값 n에 도달하면은 값을 출력하고 함수를 끝내게 된다. 

 

c++ 코드 :

//
//  10974_all_ permutation.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/27.
//

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


using namespace std;
vector<int> v;
bool visit[9];
int n;

void make_permu_dfs(){
    if(v.size() == n){ //3
        for(int i = 0; i < n; i++){
            cout << v.at(i) << " ";
        }
        cout << endl;
        return;
    }else{
        for(int i = 1; i <= n; i++){
            if(visit[i] == false){
                visit[i] = true;
                v.push_back(i);
                make_permu_dfs();
                //cout << "pop " << v.back() << endl;
                v.pop_back();
                visit[i] = false;
            }
        }
    }
}

int main(){
    cin >> n;
    memset(visit, false, sizeof(visit));
    make_permu_dfs();
    return 0;
}