백준 10974번 [모든 순열](C++) -yes6686- 티스토리

백준 문제 풀이: 10974번 [모든 순열]

---

문제 링크: https://www.acmicpc.net/problem/10974

문제 설명:

자연수 N이 주어질 때, 1부터 N까지의 모든 순열을 사전 순으로 출력하는 문제입니다. N은 최대 8이며, 모든 순열을 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int visited[9]; // 방문 여부를 저장하는 배열

// DFS를 사용하여 모든 순열 생성
void dfs(int x, int d, string s) {
    if (d > x) { // 길이가 N인 순열이 생성된 경우
        for (int i = 0; i < s.size(); i++) {
            cout << s[i] << ' '; // 순열 출력
        }
        cout << '\n';
        return;
    }

    for (int i = 1; i <= x; i++) {
        if (visited[i] == 0) { // 아직 사용하지 않은 숫자라면
            visited[i] = 1; // 방문 표시
            dfs(x, d + 1, s + to_string(i)); // 다음 숫자를 추가
            visited[i] = 0; // 방문 해제
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 입력: N
    dfs(n, 1, ""); // DFS 호출
}

---

코드 설명

위 코드는 DFS를 사용하여 모든 순열을 생성하고 출력합니다. 주요 로직은 다음과 같습니다:

1. DFS로 순열 생성: 현재까지의 순열을 문자열로 저장하며, 길이가 N이 될 때까지 재귀적으로 호출합니다.
2. 방문 체크: 이미 사용한 숫자는 `visited` 배열을 통해 중복 선택을 방지합니다.
3. 결과 출력: 길이가 N인 순열이 완성되면 각 숫자를 출력합니다.

시간 복잡도:

• DFS로 모든 순열을 탐색하므로 O(N!)의 시간 복잡도를 가집니다.

---

결과

위 코드는 입력된 N에 대해 1부터 N까지의 모든 순열을 사전 순으로 정확히 출력합니다. 추가적인 최적화나 대체 구현 방식이 있다면 댓글로 공유 부탁드립니다!