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

 

문제

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

입력

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

 

출력

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

 

접근 방식

 

모든 순열을 구하는 문제이기 때문에 처음에는 next_permutation으로 모든 순열을 구했다

그리고 백트래킹 문제인만큼! 백트래킹으로도 풀어보았다

백트래킹은 두가지 배열을 이용해서 풀었다

사용했는지 여부를 확인하는 배열과 현재 인덱스에 어떤 값이 들어가는지 저장할 배열을 사용했다

 

 

코드

 

1. next_permutation

#include<bits/stdc++.h>
using namespace std;

int N;
int main() {
    cin>>N;

    int arr[N];
    for(int i=1; i<=N; i++) arr[i-1] = i;

    do {
        for(int i=0; i<N; i++) cout<<arr[i]<<" ";
        cout<<'\n';
    }
    while(next_permutation(arr, arr+N));
}

 

 

2. 백트래킹

#include<bits/stdc++.h>
using namespace std;

int N;
int visited[9], num[9];

void sol(int cnt) {
    if(cnt == N) {
        for(int i=0; i<N; i++) cout<<num[i]<<" ";
        cout<<'\n';
        return;
    }
    for(int i=1; i<=N; i++) {
        if(!visited[i]) {
            visited[i] = true;
            num[cnt] = i;
            sol(cnt+1);
            visited[i] = false;
        }
    }
}
int main() {
    cin>>N;

    memset(visited, false, sizeof(visited));

    sol(0);
}

 

아래 - 1, 위 - 2로

둘다 시간은 똑같지만 next_permutation을 이용한풀이가 코드가 절반임을 알 수 있다 ~.~

공부하는 김에 백트래킹도 이용하면 좋지만 코테에서는 효율적으로 푸는 것이 좋을 듯하다