[BaekJoon]10974번: 모든 순열

브루트포스 알고리즘

문제

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

입력

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

출력

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

예제 입력 1 
3

예제 출력 1 
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

💻코드

순열 구현 알고리즘

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

void Permutation(int arr[], bool visited[], int output[], int depth, int n, int r){
    if(depth == r){
        for(int i = 0; i < depth; i++) cout << output[i];
        cout << "\n"; 
        return;
    }
    else{
        for(int i = 0; i < n; i++){
            if(visited[i] != true){
                visited[i] = true;
                output[depth] = arr[i];
                Permutation(arr, visited, output, depth+1, n, r);
                visited[i] = false;
            }
        }
    }
}

문제 풀이 코드

/*
* [백준 10974] 모든 순열
* N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

* [알고리즘]
* 완전탐색 알고리즘 : 가능한 모든 경우의 수를 모투 체크해 정답을 찾는 방법
* 그리디와 자꾸 헷갈릴 때가 있는데, 그리디는 현 로컬 시점에서 최적해를 따라 최종적 해답에 이르는 방법이고,
* 완전 탐색은 정말 경우 하나하나 다 따져보는 방법
*
*
*/

#include<iostream>	
#include<algorithm>
#include<vector>
#include<string>	

using namespace std;

int N;
int nums[9];
int visited[9];

void Permutation(int n) {
	if (n == N) {
		for (int i = 0; i < N; i++) cout << nums[i] << " ";
		cout << "\n";
		return;
	}
	for (int i = 0; i < N; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			nums[n] = i + 1;
			Permutation(n + 1);
			visited[i] = 0;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> N;
	Permutation(0);
	
	return 0;
}