82. 순열구하기 [DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

풀이 

- 순열 경우의 수를 DFS로 구현

- A배열에 들어있는 원소들을 n개의 가지로 뻗어나가면서 방문한다.

=> 이때 ch가 1이면 방문한 것이므로 제외하고 방문하지 않았을 시 res[L](경로 출력위함)에 a[i]값을 넣고 ch[i]=1로 바꾼다.

=> DFS(L+1)로 다음레벨로 내려간다.

=> 한 경로가 끝난후에 (L==r) 레벨별로 방문한 정점을 담아놓은 res배열을 출력하고, 경로의 개수를 +1한다.

=> 그 이후 puts("")로 행을 바꿔준다.

=> DFS 함수가 끝난 후 경로 개수 cnt를 출력한다.

 

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, r, cnt=0;
int a[20], res[20], ch[20];

//82. 순열구하기 (DFS)
void DFS(int L){
    if(L==r){
        //마지막 레벨까지 가면 경로를 출력
        for(int j=0;j<L;j++){
            printf("%d ", res[j]);
        }
        cnt++;
        puts("");
    }else{
        for(int i=1;i<=n;i++){
            if(ch[i]==0){
                //방문한다
                res[L]=a[i];
                ch[i]=1;
                DFS(L+1);
                ch[i]=0;
            }
        }
    }
}


int main(){
    scanf("%d %d", &n, &r);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    DFS(0);
    printf("%d\n", cnt);
    return 0;
}