Backtracking

모든 경우의 수를 전부 고려하는 알고리즘이며, 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 

DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘

 

---

 

한정 조건

• 백트래킹은 모든 경우의 수에서 한정 조건에 유망한 promissing 경우를 탐색하는 것이기 때문에 완전탐색기법인 BFS 나 DFS 모두 구현이 가능하다.
• 하지만 백트래킹의 특성에서 한정 조건에 부합하지 않다면 이전 수행으로 돌아와야하기 때문에 BFS보다 DFS가 구현에 편하다.
• 백트래킹을 구현할 때 가장 중요한 것은 한정 조건이다. 한정 조건을 걸어 완전 탐색에서 유망하지 않은 시도를 걸러내는 것이 백트래킹의 본질이다.

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

is_used = [False] * (n + 1)
permutaion = [0] * m    

def back_tracking(k):
    global permutaion
    global is_used

	# base condition
    if k == m:
        print(' '.join(map(str, permutaion)))
        return
    
    for i in range(1, n + 1):
        if not is_used[i]: # 한정 조건에 유망하다면
          permutaion[k] = i
          is_used[i] = True
          back_tracking(k + 1)
          is_used[i] = False # 이전 수행으로 돌아가기

back_tracking(0)

# N-Queen 문제
N = int(input())

board = [0] * N
count = 0

def back_tracking(row):
    global board, count
    
		# base condition
    if row == N:
        count += 1
        return
    
    for c in range(N):
        board[row] = c

        if not promissing(row):
            back_tracking(row + 1)

# 한정 조건
def promissing(row):
  for r in range(row):
      if board[row] == board[r] or abs(row - r) == abs(board[row] - board[r]):
          return False
  return True

back_tracking(0)
print(count)