[BOJ/백준] 10974 모든 순열

● [문제번호 10974] 모든 순열

https://www.acmicpc.net/problem/10974

10974번: 모든 순열

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

: 재귀

 

● 풀이 과정

: 이전에 있었던 다음 순열, 이전 수열 문제 보다는 N과 M (1) 문제와 거의 동일했다.

 

: 특별한 것 없이 재귀를 이용한 DFS의 형태로 구현했다.

 

● 주의 할 것

: NULL

 

● 참고 할 것

: 15649 N과 M (1)

https://pirateturtle.tistory.com/243

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// num : 출력할 순열을 저장
// visited : num 배열에 있는 지 표시 (true : 있음 / false : 없음)
int num[9] = {0, };
bool visited[9] = {false, };
int N;

// 재귀를 이용한 순열 출력 함수
void permutation(int cnt)
{
    // 중복없이 모든 숫자가 num배열에 들어간 경우
    if(cnt == N)
    {
        for(int i = 1; i <= N; i++)
            cout << num[i] << " ";
        cout << "\n";
        return ;
    }
    
    // 1부터 순서대로 num배열에 추가
    for(int i = 1; i <= N; i++)
    {
        // num배열에 없는 경우
        if(!visited[i])
        {
            // 1. num 배열에 있다고 표시
            // 2. num 배열에 원소 추가
            // 3. 재귀
            // 4. num 배열에 없다고 표시
            visited[i] = true;
            num[cnt + 1] = i;
            permutation(cnt + 1);
            visited[i] = false;
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // num 배열에 아무 숫자도 없으므로 0부터 시작
    permutation(0);
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [520 - 브루트 포스 - 순열] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10972	다음 순열	https://pirateturtle.tistory.com/237
2	10973	이전 순열	https://pirateturtle.tistory.com/238
3	10974	모든 순열	https://pirateturtle.tistory.com/239
4	10819	차이를 최대로	https://pirateturtle.tistory.com/240
5	10971	외판원 순회 2	https://pirateturtle.tistory.com/241
6	6603	로또	https://pirateturtle.tistory.com/242