[Python-CodingTest] 6-6. 중복순열 구하기 (DFS: 깊이우선탐색)

중복순열 구하기

문제 정리

입력

3 2

처리 과정

1. 중복순열 결과 리스트(res[L])에 값 넣고 DFS(L+1)로 재귀
2. L이 m(=2)이 되면 res 출력
3. 총 개수를 카운트하기 위한 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: 전역변수를 사용하기 위한 키워드

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기