Algorithm - 순열 구하기(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[순열 구하기(DFS)]

 

1부터 N까지 번호가 적힌 구슬이 있다.

이 구슬 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력하는 프로그램을 작성하시오.

(단, 구슬의 중복을 허용하지 않음)

 

 

*입력 설명

첫 번째 줄에 자연수 N(3 ≤ N ≤ 10)과 M(2 ≤ M ≤ N)이 주어진다.

 

*출력 설명

첫 번째 줄부터 결과 값을 출력한다.

마지막 줄에는 총 경우의 수를 출력한다.

단, 출력순서는 사전순서 및 오름차순으로 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_50.txt', 'rt')

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

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

'''

 

input_50.txt(입력)

3 2

 

 

중요내용

1. 중복순열 구하기 문제와 기본적인 원리는 유사하지만, 체크변수를 사용하여 중복을 허용하지 않는 부분이 추가되었다.
2. 즉, 사용된 구슬 번호는 체크변수에서 1의 값을 가지게 만들어 이후에는 해당 값을 중복으로 사용하지 못하게 하는 것이다.
3. 단, 재귀함수 DFS()가 종료되어 복귀위치로 돌아갈 때에는 체크변수에서 사용된 구술 번호를 다시 0으로 만들어야 한다. (순열의 다른 조합을 고려할 때 해당 구슬 번호를 사용하기 위함)
4. DFS(L+1)를 기준으로 ch[i] = 1은 구슬 번호가 사용되었음을 표기하는 코드이고, ch[i] = 0은 사용된 구슬번호를 다른 순열조합에서 사용하기 위해 기본 값(0)으로 초기화하는 코드이다.
5. 변수 res는 순열 조합의 결과를 저장하는 변수이다.
6. DFS() 함수의 인자 L은 순열 조합의 자리수를 의미한다. (단, L은 m과 의미는 같지만 리스트의 인덱스 번호로 사용되기 때문에 두 변수의 값은 일치하지 않음)