[백준] 15649 N과 M(1) python - DFS, 백트래킹

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

15649번: N과 M (1)

 

예제 입력:
3 1

 

예제 출력:
1
2
3

---

🔵백트래킹

백트래킹 이론을 아무리 봐도 이해가 가지 않아 N과M 문제의 코드를 먼저보고 분석해보았다.

백트래킹이란 DFS에 기반을 두고 있는 전략으로, 불필요한 경우를 배제하며 원하는 답에 도달할 때까지 탐색하는 알고리즘이다.

백트래킹 탐색 이미지

DFS를 기반으로 하고있기 때문에 스택(stack)을 이용해 퇴각하며 다음 탐색을 진행한다.
백트래킹 같은 경우 기본적으로 모든 경우의 수를 탐색하는 완전탐색(브루트포스)전략을 취하지만, 처리속도를 향상시키기 위해 가지치기(pruning)라는전략을 이용한다.

 

정답코드:

import sys
input = sys.stdin.readline

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

def backtracking():
    if len(res) == m:	#종료조건
        print(' '.join(map(str, res)))

    for i in range(1, n+1):
        if i not in res:
            res.append(i)
            backtracking()
            res.pop()

backtracking()

 

백트래킹의 가장 중요한 키워드
-> 가능한 모든 경우를 실행한다

모든경우를 실행하는 가장 좋은 경우는 
-> 트리형태

첫번째숫자는 뭘로 할거냐?
n은 선택된 숫자의 길이(갯수)
*우리가 구해야하는것: 길이M짜리 수열