문제
순열 구하기
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
답안
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()) #n은 구슬에 적힌 번호 1부터 n까지
res=[0]*n
ch=[0]*(n+1)
cnt=0
DFS(0)
print(cnt)
-ch 리스트
체크 리스트
def DFS(L):
else:
for i in range(1, n+1):
if ch[i]==0:
~~
ch[i]==0일 때만 코드가 작동하도록 설계--> 이미 사용된 숫자가 또 포함되면 안되기 때문이다
ch 리스트는 함수가 끝나면 초기화 되어야 한다.
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(L+1)에서 L+1==m이면 함수가 끝난다. 따라서 다시 DFS(L)로 돌아오고 ch[i]=0 코드를 통해
다시 초기화된다.
-result 리스트
말 그대로 결과값을 넣는 리스트이다.
def DFS(L):
else:
for i in range(1, n+1):
~~(생략)
res[L]=i
~~~('')
DFS(L)에서 L은 순서, 계층을 의미한다. 결과값 리스트나 어떤 값이 아닌 것이다.
따라서 res[L]=i로 지정하는 것은 res리스트의 L번째 값에 1부터 n+1까지 모두 지정해서 결과값을
도출하는 것이다. ch[i]=1인 경우를 제외하고!
-res n개의 원소 VS ch (n+1)개의 원소
res는 그냥 결과값이므로 0번째부터 count해서 도출하면 되지만 ch리스트는 원소의 순서가 곧
구슬 번호이기 때문에 n+1개를 설정해야 한다. 예를 들어 ch[2]==1인 경우 2번 구슬이 이미 쓰였다는 뜻이다
조합 구하기 (0) | 2021.08.25 |
---|---|
수열 추측하기 (0) | 2021.08.25 |
6.7 동전 교환-Cut Edge Tech (0) | 2021.08.13 |
6.6 중복 순열 구하기(DFS) (0) | 2021.08.11 |
6.5 바둑이 승차(DFS) (0) | 2021.08.10 |
댓글 영역