[알고리즘] DFS와 백트래킹 backtracking(+ N queen, 부분수열의 합)

백트래킹이란?

• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
• 최적화 및 결정 문제의 해법이 됨

DFS

• 백트래킹의 일종이며, 재귀를 활용함

N*N Queen 문제

• N*N의 체스판에 queen N개를 놓을 때, 서로 모두 공격 불가능한 상태로 배치하는 경우의 수를 체크하는 문제
  - queen은 가로, 세로, 대각선 모두 공격가능!
• 유튜브 해설
  
• 블로그 해설

code

N  = int(input())

ans = 0
col = [0] * N

def check(x):
  for i in range(x):
    if col[x]==col[i] or (x-i ==abs(col[x]-col[i])) : # 이전까지 중 하나라도 under attack 이면
      return False
  return True

def backtrack(x):
  global ans
  if x==N:
    ans+=1
    return 
  else:
    for i in range(N): # 0-n-1 까지 각각의 node 별 탐색
      col[x]=i # x는 인풋, i 는 itertating

      if check(x): # checking 시 under attack 상태가 아니라면
        backtrack(x+1) # 다음 자식 노드로 넘어감

backtrack(0)
print(ans)

Sum of subset 문제

유튜브 문제풀이(양수 조건만 걸려있어서 조금 다름)

백준 1182: 부분수열의 합

import sys

inp = sys.stdin.readline
n, s = map(int,inp().split())
sets = list(map(int, inp().split()))
ans=0
def backtrack(x,subset):# x는 sets에 대응될 index
    global ans
    if x>=n:
        return

    subset +=sets[x] #input으로 받은 부분합에 더함

    if subset==s:
        ans+=1
    # if subset<s: # 값들이 양수로만 이루어져 있을 경우 활용하면 좋을 조건
    backtrack(x+1, subset) # 해당 값을 더한 부분합.

    backtrack(x+1, subset-sets[x]) # 안더한 부분합.

backtrack(0,0)
print(ans)

회고😁

• 재귀방식과 DFS 가지치기를 머릿속에 그리며 알고리즘을 짜는 것이 핵심.
• 중간중간 if문으로 불필요한 가지를 더이상 탐색하지 않도록 하면 더 효율적인 알고리즘이 될 수 있음.