[알고리즘] 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 문제
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문으로 불필요한 가지를 더이상 탐색하지 않도록 하면 더 효율적인 알고리즘이 될 수 있음.
Author And Source
이 문제에 관하여([알고리즘] DFS와 백트래킹 backtracking(+ N queen, 부분수열의 합)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@crosstar1228/알고리즘-DFS와-백트래킹-backtracking저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)