섹션 6. 순열 구하기

---

DFS를 이용한 풀이

def dfs(l):
    global cnt
    if l == m:
        print(*res)
        cnt += 1
        return

    for i in range(1, n + 1):
    	#내 처음 코드. in연산자를 쓰기 때문에 체크리스트를 쓰는 게 더 효율적임.
        # if i in res:
        #     continue
        # res[l] = i
        # dfs(l + 1)
        # res[l] = 0
        
        #중복순열이 아니기에 res에 중복된 요소가 들어가는 걸 방지하기 위해 체크리스트 사용
        #다음 레벨에서 고를 수 있는 수는 부모레벨에서 선택한 값 제외 모두 가능
        if ch[i] == 0:
            ch[i] = 1
            res[l] = i
            dfs(l + 1)
            ch[i] = 0


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

cnt = 0

dfs(0)
print(cnt)

 

라이브러리를 이용한 풀이

from itertools import permutations
n, m = map(int, input().split())

seq = [i for i in range(1, n+1)]

cnt=0
for v in permutations(seq, m):
    cnt+=1
    print(*v)

print(cnt)

 

피드백

라이브러리를 이용하는게 훨씬 편하지만 테스트에서 사용을 금지할 수도 있기 때문에 DFS로 구하는 방법은 무조건 익혀두고 가자.