백준 10974 - 모든 순열
Updated:
C++
10974 번 - 모든 순열
문제
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. 문제 출처
DFS의 가장 기본적인 문제이다.
DFS를 연습하기 좋은 문제.
접근 방법
DFS를 이용하여 모든 순열을 구한다.
구현
필요한 배열은 뽑은 수를 저장할 arr과, 그 수가 선택이되었는가 여부를 확인하는 visited 2개가 있다.
visited 배열은 그 자리 0 ~ n - 1 까지 각각 1 ~ n을 나타낸다.
DFS()
이 함수의 매개변수 lv은 현재 몇개를 수를 뽑았는가를 나타낸다.
만약 lv이 n이 되면 n개의 수를 뽑은 것이므로 출력을 하고 return한다.
수를 뽑는 방법은, 0에서 n개까지 반복문을 통해 하나씩 선택한다. 만약 선택한 수 i가 visited 배열을 통해 한번도 방문한 적이 없으면, 그 수를 arr[lv]에 저장하고, 그 수의 위치 visited[i]에 1로 설정하여 뽑았다고 명시한다.
에시를 들며 설명하면,
제일 처음 DFS(0)으로 호출하였으므로, lv은 0이다. 그리고 처음 수는 1이므로, 1을 뽑고 visited[0]을 true로 설정하여 1이라는 수는 뽑혔다고 명시하고, arr[0]은 1을 넣는다.
DFS(1)을 다시 호출하고 반복문으로 들어오면, visited[0]이고 visited[1]은 false이므로 숫자 2를 선택하여 arr[1]에 2를 넣는다.
이를 반복하면 제일 처음 수열인 1 2 3 .. n 이 만들어 진다.
DFS()가 종료되면 visited[i]를 false로 만들어 주므로, 다음 수열은 1 2 3 … n , n - 1 처럼 자리가 바뀌고, 사전순으로 정렬이 된다.
코드
#include <iostream>
#include <vector>
using namespace std;
int n, arr[8], visited[8];
void DFS(int lv);
void doPrint();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
DFS(0);
}
void DFS(int lv) {
if (lv == n){ // 만약 선택한 숫자가 n개면 출력. 만약 n이 미만의 수 k이면 k개 수를 뽑는 조합으로 사용가능
doPrint();
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
visited[i] = 1;
arr[lv] = i + 1;
DFS(lv + 1);
visited[i] = 0;
}
}
}
void doPrint() {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << "\n";
}
