[파이썬 알고리즘 문제풀이] - Section6 / 완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초 - 8

⚽ 순열 구하기

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
# sys.stdin = open("input.text", "rt")

#조합
N, M = map(int, input().split())

res = [0] * M
cnt = 0
ch = [0] * (N+1) #해당 값을 사용했는지 안했는지 확인하는 리스트
def DFS(L):
    global cnt
    if L == M: #종료 조건. M개 뽑으면 끝
        for x in res:
            print(x, 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 #백트랙킹으로 돌아오면 해당 값 이제 안쓴걸로 초기화

DFS(0)
print(cnt)
            

⚽ 코멘트

순열이란 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 (나열하는) 것을 말한다.
처음에 결과 리스트를 모두 초기화를 시켜 놓는다.

처음 DFS(0) 역시 중복 순열을 할 때와 동일하게 가지 뻗기를 진행한다. 근데 DFS(0)에서 1을 넣었다면 DFS(1)에서는 1을 선택하면 안된다. (중복안됨) 그렇기에 체크 리스트에서 해당 값을 사용했는지를 확인해서 확인 안한 것들만 확인하는 것이다.

이런 식으로 중복 순열과 다른 것은 체크 리스트에서 이전에 사용했던 것을 사용하면 안되는 것이다.

• 또한 백트랙킹 과정에 있어서 돌아올 때 해당 값의 체크 리스트를 풀어주어야만 한다.

이 과정만 이해했다면 순열 문제를 쉽게 해결할 수 있을 것이다.