[Python-CodingTest] 6-6. 중복순열 구하기 (DFS: 깊이우선탐색)
중복순열 구하기
문제 정리
입력
3 2
처리 과정
- 중복순열 결과 리스트(
res[L]
)에 값 넣고DFS(L+1)
로 재귀 - L이 m
(=2)
이 되면res
출력 - 총 개수를 카운트하기 위한 global 변수
cnt
출력
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
9
풀이
import sys
sys.stdin = open("./input/in6.txt", "rt")
# input=sys.stdin.readline # 입력량이 많을 때 속도 증가
# str=input().rstrip()
def DFS(L):
global cnt
if L==m: # 하나의 중복순열 완성
for x in res:
print(x, end=' ')
print()
cnt+=1
else:
for i in range(1,n+1): # 1부터 n까지
res[L]=i # 중복순열 리스트에 값(1~n) 넣기
DFS(L+1)
if __name__=="__main__":
n,m=map(int,input().split())
res=[0]*m # 중복순열 결과 리스트
cnt=0
DFS(0)
print(cnt)
정리
global
: 전역변수를 사용하기 위한 키워드
💛 개인 공부 기록용 블로그입니다. 👻