[문제]
10974번: 모든 순열 (acmicpc.net)
10974번: 모든 순열
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.
www.acmicpc.net
[문제 풀이]
백트래킹을 이용해서 모든 순서를 파악하자.
숫자 1부터 n까지를 넣어야 하고 반복되는 숫자는 없어야 한다.(19~22)
만약에 1번이라도 넣었으면 해당 숫자를 방문했다고 체크해주자(23)
answer에 넣은 뒤 재귀를 이용해 다시 반복하자(24~25)
해당 재귀가 끝나면 마지막에 넣은 숫자를 뺀뒤에 방문표시를 다시 false로 바꾸자.(26~27)
[코드]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include<iostream>
#include<vector>
#define endl "\n"
using namespace std;
vector<int> answer;
bool visit[9];
void backtracking(int n, int m){
if(m == n){
for(int i = 0;i<n;i++){
cout<<answer[i]<<" ";
}
cout<<endl;
return;
}
for(int i =0;i<n;i++){
if(visit[i] == true){
continue;
}
visit[i] = true;
answer.push_back(i+1);
backtracking(n,m+1);
answer.pop_back();
visit[i] = false;
}
}
void solve(int n){
backtracking(n,0);
}
int input(){
int n;
cin>>n;
return n;
}
int main(){
int n = input();
solve(n);
return 0;
}
|
cs |