[백준] 15649번 N과 M (1) - 파이썬

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

15649번: N과 M (1)

풀이

DFS의 일종인 백트래킹 알고리즘입니다. 

사실상 백트래킹은 구현문제에 가깝습니다. 생각하기는 쉬우나 코드를 제어해주는 부분을 막상 작성하려하면 마음처럼 되지않을 경우가 많습니다. 아래 코드는 arr에 숫자를 하나씩 넣어줘서 조건에 만족하는 m이 나올 경우 출력해주는 코드이며, for문을 통해 arr에 들어가지않은 코드를 찾아줍니다. 재귀와 백트래킹에 대한 이해도가 요구되는 문제입니다.

# 15649번 N과 M (1)
n, m = map(int, input().split())
arr = []

def dfs():
    if len(arr) == m:
        print(' '.join(map(str, arr)))
        return
    for i in range(1, n+1):
        if i not in arr:
            arr.append(i)
            dfs()
            arr.pop()
dfs()

출력결과