❗️[알고리즘]순열 구하기

문제

1부터N까지번호가적힌구슬이있습니다.이중 M개를뽑아일렬로나열하는방법을모두 출력합니다.

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

입력예제1

3 2

출력예제1

1 2
1 3
2 1
2 3
3 1
3 2
6

[해설 코드]

def DFS(L):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i],end=' ')
        cnt+=1
        print()
    else:
        for i in range(1,n+1):
            if ch[i]==0:
                ch[i]=1
                res[L]=i
                DFS(L+1)
                ch[i]=0


if __name__=="__main__":
    n,m=map(int,input().split())
    cnt=0
    ch=[0]*(n+1)
    res=[0]*m
    DFS(0)
    print(cnt)

1. 각 각의 DFS()는 L레벨 전 L-1은 방문하지말아야 한다. 따라서, ch[]배열을 이용해서 각 L에서의 방문 여부를 체크한다.
   2.이 떄, DFS()가 노드의 중단조건 레벨까지 가면 ch[i]=0을 통해 방문 여부를 다시 초기화해준다.
2. if L==m으로 중단조건이 만족하면 res배열에 저장된 원소를 차례로 출력.