[Python Algorithm] 완전탐색(DFS) - 순열 구하기

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 

 

 

 

📖 문제 : 순열 구하기

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

 

import sys

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





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

 

 

⭐️ Point ! ⭐️

• DFS()함수의 밑의 지점은 back을 하고 돌아온 시점이다. 
  따라서 DFS[L+1] 전에 ch[i] = 1을 해주어 값에 추가해주고 (예를 들어, 1을 넣고 2를 추가해주고 {1,2})
  DFS[L+1] 후에 ch[i] = 0을 해주어 ({1,2} 를 -> {1,3}으로 만들기 위해 {1}로 만들어주는 것 ! => 백트래킹 !)

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이