(C/C++) 백준 10974번 - 모든 순열

문제 출처:https://www.acmicpc.net/problem/10974

10974번: 모든 순열

1. 코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int N;
int arr[10];
bool check[10];
 
void visited(int num) {
    if (num >= N) { //입력 받은 수 까지 순열을 탐색했으면
        for (int i = 0; i < N; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }
    else {
        for (int i = 1; i <= N; i++) {
            if (check[i] == true)
                continue;
            check[i] = true;
            arr[num] = i;
            visited(num + 1); 
            check[i] = false; // 출력을 해주면 숫자 다시 사용가능하게 초기화
        }
    }
}
 
int main() {
    scanf("%d", &N);
    visited(0);
    return 0;
}

 

2. 해결 과정

1~N까지 모든 수가 나타나는 순열을 출력해주면 되는 문제였다. 순환 알고리즘을 이용하면 풀 수 있었다.

1) N이 3이라고 하면 순환의 첫번째 값이 1이라고 하자

2) 순환 두번째에 올 수 있는 경우는 1,2,3이다. 1은 사용하고 있으므로 2의 탐색을 진행

3) 세번째 값에 올 수 있는 경우는 1과 2는 이미 사용하고 있으므로 3밖에 없다.

1->2->3 출력

4) 상위 노드로 돌아가서 두 번째 값이 3인 경우에 대해 탐색을 진행

5) 순환 3번째는 이전에 사용한 1과 3을 제외한 2만 사용 가능

1->3->2 출력

모든 순열을 위와 같은 방법으로 표시해주면 된다.

 

3. 느낀점

순열 출력을 하는 것에 애를 먹었다. 다른 블로그들의 도움을 받으려고 했는데 next_permutation 이라는 자체 함수를 사용하면 순열을 구할 수 있다는 것을 알게 되었다. 아직 함수에 대해서는 알지 못해서 직접 순열을 구현하고자 했다.

함수를 사용하면 더 간단(?)하게 해결 될 것 같다.

• next_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.

// 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝

 bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

// 아래처럼 직접 비교함수를 넣어줘도 가능

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);