[백준/Python] 15652 N과 M (4)

[백준/Python] 15652 N과 M (4)

정답 코드 및 설명

def DFS(N, M, sequence=[], start=1):
    if len(sequence) == M:
        print(' '.join(map(str, sequence)))
        return
    
    for i in range(start, N + 1):
        sequence.append(i)
        DFS(N, M, sequence, i)  # i를 시작으로 하여 중복 선택을 허용
        sequence.pop()

N, M = map(int, input().split())
DFS(N, M)

"N과 M (1)"에서는 각 숫자를 수열에서 단 한 번만 사용할 수 있었지만, "N과 M (3)"에서는 같은 숫자를 여러 번 사용할 수 있다는 점이 다르다. 즉, 이 문제에서는 1부터 N까지의 자연수 중에서 중복을 허용하여 M개를 고른 수열을 생성해야 한다.

문제 해결 방법

1. 재귀 함수 정의: 재귀 함수에서는 현재까지 선택된 수열을 매개변수로 받습니다.
2. 종료 조건: 현재까지 선택된 수열의 길이가 M이 되면, 수열을 출력하고 재귀 호출을 종료한다.
3. 재귀적 탐색:
   1부터 N까지 각 숫자에 대해 수행
   현재 수열에 숫자를 추가하고, 재귀 호출을 한다. 이때, 중복을 허용하므로, 이미 선택된 숫자를 다시 선택할 수 있다.
   재귀 호출이 반환되면, 마지막에 추가된 숫자를 제거하여 다음 숫자 선택을 위해 수열을 이전 상태로 되돌린다.

코드 설명

• DFS(N, M, sequence=[]) 함수는 주어진 N과 M에 대해, 현재까지 선택된 수열 sequence를 기반으로 동작한다.
• 함수가 호출될 때마다, sequence의 길이가 M인지 확인한다. M이라면 현재 수열을 출력하고 재귀 호출을 종료한다.
• for 루프에서는 1부터 N까지의 각 숫자를 순회한다. 이때, 중복을 허용하기 때문에, 이미 sequence에 있는 숫자도 다시 선택할 수 있습니다.
• 각 숫자를 sequence에 추가하고, DFS를 재귀적으로 호출한다. 이후, 백트래킹을 위해 sequence에서 마지막 숫자를 제거한다.