순열
순열이란 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 (나열하는) 것을 말한다.
- 하나의 원소에 대하여 선택하면 더이상 선택 x
⚽ 순열 구하기
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)
⚽ 코멘트
해당 문제를 보면..
이전까지의 DFS로 상태트리 시각화하는 것은 같다.
처음에 결과 리스트를 모두 초기화를 시켜 놓는다.
처음 DFS(0) 역시 중복 순열을 할 때와 동일하게 가지 뻗기를 진행한다. 근데 DFS(0)에서 1을 넣었다면 DFS(1)에서는 1을 선택하면 안된다. (중복을 허용하지 않고 일렬로 뽑는 것이기에) 그렇기에 체크 리스트에서 해당 값을 사용했는지를 확인해서(중복 확인) 사용하지 않은 값들만 그 다음 가지 뻗기에서 사용하면 된다!
⚽ 이런 식으로 중복 순열과 다른 것은 체크 리스트에서 이전에 사용했던 것을 사용하면 안되는 것이다.
- 또한 백트랙킹 과정에 있어서 돌아올 때 해당 값의 체크 리스트를 풀어주어야만 한다.
이 과정만 이해했다면 순열 문제를 쉽게 해결할 수 있을 것이다.
for i in range(1, N+1):
if ch[i] == 0: #사용안함 -> 사용해도 돼
ch[i] = 1 #해당 값 사용한다고 표시한 후에
res[L] = i #적용
DFS(L+1)
ch[i] = 0 #백트랙킹으로 돌아오면 해당 값 이제 안쓴걸로 초기화
위 과정이 모든 것들을 설명해준다. 1~N까지의 수 중에서 M개를 뽑는 것이기에 만약 현재 레벨(인덱스)에서 i를 뽑지 않았다면 해당 값을 사용하겠다고 말하고 (ch[i] = 1, res[L] = i) 다음 단계로 넘어간다.
- 여기서 중요한 것은 ! 백트랙킹으로 돌아왔을 때 이제 해당 값을 사용 안한걸로 초기화 해줘야 하는거 잊지말자 !
