[Algorithm] 백트레킹 개념, BOJ # 15649번

 

 

 

 

Back Tracking

"가능한 모든 방법을 탐색하겠다."

 

 

 

---

 

 

 

Back Tracking 이란?

현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책 후보를 찾되, 가능성이 없는 경로는 사전에 차단(Purning)하여 효율을 높이는 알고리즘이다.

 

 

비슷한 알고리즘으론 DFS(완전 탐색 방법)가 있다.

하지만 이 알고리즘은 말 그대로 모든 경로를 정직하게 탐색하므로, 가능성이 없는 경로까지도 깊게 파고들어 가 효율이 떨어진다. 

 

 

문제 Tip

DFS로 경로를 탐색하던 과정에서, 조건문 등을 걸어 가지치기를 하는 방식으로 가야 한다.

 

 

 

---

 

 

 

BOJ # 15649번 : N과 M (1)

 

 

 

 

백트레킹는 기본적으로 재귀 문제이다.

이를 잘 생각하며 풀어보길 바란다.

 

 

 

통과 예시

 

import sys
n, m = map(int, sys.stdin.readline().split()) 
a = []

def solution():

  if len(a) == m:
    print(' '.join(map(str, a)))
  
  for i in range(1, n+1):
    
    if i in a:
      continue
    
    a.append(i)
    solution()
    a.pop()


solution()