[파이썬, Python] 백준 15649: N과 M (1)

문제

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

15649번: N과 M (1)

코드

n, m = map(int, input().split())

s = []

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

설명

처음에는 간단한 다중 반복문으로 구성하려고 했으나 수가 커질수록 불가능에 가까웠고,
검색을 통해 dfs를 베이스로 한 백트래킹 방식을 이용하여 풀었다.
dfs는 원래 가장 하위 노드까지 탐색을 진행하지만,
백트래킹의 경우 가능성이 없는 노드는 하위 노드를 추가로 탐색하지 않고 다른 노드를 탐색한다.
이를 '가지치기'라고 한다.

1부터 n+1까지의 수들 중에서,
반복문에서 리스트에 없는 수를 대상으로만 탐색을 진행하고,
리스트에 있는 수의 개수가 m보다 작으면 수를 추가하는 과정을 거치고,
리스트의 수의 개수가 m과 같아지면 그 리스트를 출력한다.
이후 마지막에 들어온 수를 제거하여 계속 반복한다.
재귀를 통해 모든 수를 확인하면 종료된다.