[BOJ/C++] 10974번 모든 순열

분류

브루트포스 알고리즘, 백트래킹

문제 설명

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

 

풀이

dfs를 이용해서 점차 깊게 확인 후 더이상 가지 못할때 값을 출력함. 아래 사진 참고

출처: https://fieldanimal.tistory.com/26

코드

#include <iostream>
#include <vector>
using namespace std;
int visited[9], N;
vector <int> v;

void dfs() {
    if (v.size() == N) {
        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << "\n";
    }

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            v.push_back(i);
            dfs();
            visited[i] = 0;
            v.pop_back();
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    fill(visited, visited +9, 0);
    dfs();
}