[파이썬 15651] 백준 N과 M (3) DFS 중복순열

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

DFS 문제를 풀 때는 그림을 그려서 이해하면 접근이 조금 쉬워진다.

중복순열은 m개를 선택해 나올 수 있는 모든 수의 조합을 나열하면 된다.

예를 들어 3개중 2개를 택해야 하는 상황이라면 

arr[0] = 1

arr[1] = 1, 2, 3

arr[0] = 2

arr[1] = 1, 2, 3

arr[0] = 3

arr[1] = 1, 2, 3

이런형태로 출력해주면 순서대로 출력 될것임.

import sys
def DFS(L):
    if L == m :
        [print(arr[i], end=" ") for i in range(m)]
        print("")
        return
    else:
        for i in range(1,n+1):
            arr[L] = i
            DFS(L+1)

    

if __name__ == "__main__":
    n, m = map(int,sys.stdin.readline().split())
    arr = [0] * m
    DFS(0)

메인함수에서 0으로 시작해서 arr의 0 ,1 번째 인덱스의 값을 받고 DFS의 L이 m의 값(0에서 시작했으므로)이 되면 arr을 출력해주면 될 것임.

이 if문으로 일정 레벨 이상 진행하는걸 막아주지 않는다면 index오류가 날것임