해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 15650번 N과 M(2) - 백트래킹

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

문제

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

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다. 15650의 문제에서 약간 변형된 문제입니다.

https://zidarn87.tistory.com/329

2. 재귀함수를 이용하고, 출력하려는 리스트의 개수가 m개 이면 리스트의 내용을 출력하도록 합니다.

3. 재귀함수에서는 전달받은 인자인 start부터 n까지 숫자를 사용합니다. 재귀함수를 호출할 때에는 i+1을 호출하여 줍니다. 그러면 오름차순으로 리스트에 들어가게 됩니다. 

전체 코드

N, M = map(int, input().split())
lst = []

def dfs(start):
    if len(lst) == M:  # 탈출 조건
        print(' '.join(map(str, lst)))
        return

    for i in range(start, N+1):
        if i not in lst:
            lst.append(i)
            dfs(i+1)
            lst.pop()
dfs(1)