[Python] 백준 15649번, N과 M, 백트래킹(Backtracking)

• 문제 링크 : https://www.acmicpc.net/problem/15649

1. 문제

2. 코드 풀이

# 백트래킹
import sys

input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
s = []

def dfs(s):
    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)
            print(s.pop())

dfs(s)

3. 백트래킹

• 해를 찾아가는 과정에서, 해가 나오지 않을 경로를 가지 않고 다시 돌아와 다른 경로를 탐색하는 것. (= 가지치기)
• 특정 조건을 만족할 경우만 확인
• 주로 문제에서, DFS 등으로 모든 경우의 수를 찾는 과정에서, 조건문으로 답이 절대 될수 없는 상황을 정의하고, 해당 상황일 때, 다시 돌아가 다른 경로를 찾는다.