오늘은 DFS를 이용하여 순열의 경우의 수를 출력하고 가짓수도 출력하는 코드를 작성해 봅시다.
순열 이란?
고등학교 수학시간에 순열과 조합을 배웠죠.
순서를 고려하고, n개 중 r개를 중복 없이/있이 뽑는 순열
순서를 고려하지 않고, n개 중 r개를 중복 없이/있이 뽑는 조합
그 중 순열 은 순서를 고려하여 n개 중 r개를 중복 허용하지 않고 뽑는 방법 입니다.
접근방법
A={1,2,3} 에서 숫자 2개를 뽑아 순열을 만든다고 가정합시다.
순열로 만들면 결과는
1 2
1 3
2 1
2 3
3 1
3 2
총 6개가 나옵니다.
이걸 어떻게 만들까요?
우선, 뽑혀진 숫자의 배열을 res 라 하고, res의 크기는 2개를 뽑는다 했으니 2개면 됩니다. 여기까지는 중복순열과 같고, 차이점이 있다면 중복 여부를 확인하는 배열 ch 을 추가해줍니다.
1) 숫자 1이 아직 뽑히지 않았다면, 1을 순열로 만들기 위해 ch[1]=1로 체크합니다.
2) res[0]=1을 넣어 숫자 1을 순열로 만듭니다. 여기서 res 의 인덱스는 DFS의 level을 뜻합니다.
3) DFS가 종착지 까지 도착한 뒤, 프로그램 상에서 쌓여있던 남은 명령어를 pop 하면서 실행하게 됩니다. 이때, 순열에 사용되었던 숫자 1을 다시 사용하기 위해(=반납) ch[1]=0로 체크합니다.
이 과정이 이해가 된다면 어떤 변수를 어떻게 일반화 할지 생각하며, 이제 DFS로 만들어 봅시다.
코드는 아래와 같습니다.
def DFS(L):
global cnt
if L==m: #숫자 2개 다 뽑은 경우 = 종착지
for i in range(m):
print(res[i], end=' ')
print()
cnt+=1
else:
for i in range(1, n+1): #숫자는 1부터 n개 있음
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) #level 0 부터 시작
print(cnt)중복순열과 마찬가지로,
DFS(0) 일땐 res[0]에 숫자를 집어 넣고,
DFS(1) 일땐 res[1]에 숫자를 집어 넣습니다.
res 배열이 꽉 찬 경우는 곧 순열이 완성된 순간이니, 그 때 순열의 경우의 수를 출력하면 됩니다.
오늘의 게시글 끝!
