[Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-순열 구하기(DFS)

 

 

import sys
# sys.stdin=open("input", "r")
input=sys.stdin.readline    # 입력양이 많을 때 이 라인을 쓰면 입력 속도가 빨라진다
# s=input().rstrip()        # 위의 라인을 사용하게 되면 문자열을 읽을 때 줄바꿈 기호가 들어오므로 이를 날려야한다
 
def DFS(level):
    global cnt
 
    if level == m:
        for i in range(m):
            print(res[i], end=" ")
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            if check_ls[i]==1:
                continue
            res[level]=i
            check_ls[i]=1       # 쓰인 숫자는 1 체크
            DFS(level+1)
            check_ls[i]=0       # 출력이 끝나면 숫자는 다시 쓰이지 않은 상태로 돌려놓는다
 
if __name__=='__main__':
 
    n, m = map(int, input().split())
    cnt=0
    res=[0]*m
    check_ls=[0]*(n+1)      # 숫자가 중복되지 않기 위해 체크리스트 배열을 하나 만들었다
    DFS(0)
    print(cnt)