[Python Algorithm] 완전탐색(DFS) - 중복순열 구하기 (sys.stdin.readline()로 입력 빠르게 받기)

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 

 

 

 

 

📖 문제 : 중복순열 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.

 

 

입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

 

출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

 

입력예제 1

3 2

 

출력예제 1

1 1
1 2
1 3

2 1

2 2

2 3

3 1

3 2

3 3

9

 

 

import sys
input = sys.stdin.readline

def DFS(L):
    global cnt
    if L == m:
    	for j in range(m):
            print(res[j], end=' ')
            print()
            cnt+=1
        
        
    else:
    	for i in range(n+1):
            res[L] = i
            DFS(L+1)


n, m = map(int, input().split())
res = [0]*m
cnt = 0
DFS(0)
print(cnt)

 

 

⭐️ Point ! ⭐️

• input = sys.stdin.readline 추가하면 입력시 속도가 빨라진다
  
  
• 하지만 문자열 읽을 때에는 줄바꿈이 항상 같이 읽어지므로 줄바꿈을 없애주기 위해서
  s = input().rstrip() 이렇게 사용하여 입력 받기 ! 

 

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이