[백준] 15649번: N과 M(1) / Python / 브루트 포스

N과 M(1)

• 문제
  자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

• 입력
  첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

• 출력
  한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
  수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이 방법

• itertools의 permutation을 이용할 수도 있지만, 문제의 의도에 맞게 백트래킹을 구현해보자. 백트래킹은 깊이우선탐색(DFS) 방식을 기반으로, 모든 경우의 수를 탐색하는 브루트 포스 전략에서 불필요한 경우를 가지치기 해가면서 원하는 해답을 찾는 방법이다.
• 이 문제는, 반복적으로 숫자를 선택해 M개까지 골라서 수열을 완성하는 경우의 수를 모두 골라야 하는데, 여기서 가지치기가 필요한 경우는 이미 선택한 숫자를 다시 선택하는 경우이다.
• DFS 구현을 위해서는 스택 자료구조를 이용하는데, 이는 기본적으로 (재귀)함수의 동작 방식과 같다. 함수가 호출되면, 스택에 함수를 적용한 요소(결과)들이 차례대로 쌓이고=push, 함수가 종료되면 함수가 호출되기 전의 상태로 돌아간다(해당 요소들이 제거=pop된다). 재귀함수의 동작 예는 아래와 같다.
  
• 재귀 함수로 문제를 풀어보자.

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

def solve(cnt, s):
    if cnt == M: # M개를 골랐으면 종료
        print(" ".join(s))
        return
    
    for num in [str(i) for i in range(1, N + 1)]:
        if num not in s: # 이미 고르지 않은 숫자를 고르게 함
            solve(cnt + 1, s + [num])
        
solve(0, [])