백트래킹 (Backtracking)

백트래킹(Backtracking)은 해결책을 찾기 위해 모든 가능한 경우를 탐색하면서 해를 찾는 알고리즘 기법
완전탐색과 유사하지만 , 백트래킹은 불필요한 탐색을 줄이기 위해 재귀적으로 시행되며 조건에 따라 
시행 가능한 상태의 후보군과 시행 불가능한 후보군을 확인하여 시행 가능한 후보군만 탐색을 하며 현재 상태에서 가능한 모든 탐색지를 
탐색했다면 이전 상태로 돌아가 다음 시행 가능 후보군을 탐색한다.  

재귀적으로 가능한 후보군을 탐색하여 최종적으로 해결책을 찾아가는 알고리즘 

백트래킹이 알고리즘은 일반적으로 재귀 함수를 사용하여 구현-> 코드의 일반화를 통해 가독성 상승
하지만 재귀함수를 사용하면서 시간복잡도 지수시간을 가지게되어 최적의 해결책을 찾는데 효과적이지 않을 수 있음

가능한 불필요한 탐색을 줄이는 방법을 찾아내어 시간복잡도를 최적화 하는게 중요하다

백트래킹 문제

 

백준 15649 n과m(1) 문제  https://www.acmicpc.net/problem/15649

 

stack = []
def backtraking(m):
    if len(stack)==m:
        print(' '.join(map(str,stack))) # 현재 함수 종료조건 - 문제의 최대 길이 도달시 
        return
    for i in range(1,n+1):  
        if i not in stack:   #현재 값이 스택에 안들어가 있다면, 값 추가 후 재귀적으로 탐색시행
            stack.append(i)
            backtraking(m)   
            stack.pop()

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

 

백트래킹 stack의 상태

진행 가능한 모든 경우의 수를 모두 시행하며 문제의 조건인 m 도달시 현재 스택의 값을 프린트해준다.

 

백준 30242 N-Queen (eazy) https://www.acmicpc.net/problem/30242

n = int(input())

visited = list(map(int,input().split()))


diag1 = set()#왼쪽 대각선
diag2 = set()# 오른쪽 대각선
for i in range(len(visited)):
    if visited[i]!=0:
        diag1.add(i+visited[i])
        diag2.add(i-visited[i])

#퀸 대각선 움직임 체크를 어떻게할까
#행에 존재한다면 진행 못하고, 위에서부터 아래로 진행함,
# 왼쪽 대각선 (-1,-1) # 오른쪽 대각선 (-1,1)
#  왼쪽 대각선은 x+y를의 열 , 오른쪽 대각선은 x-y의 열

def queen(now):
    if now ==n:
        print(*visited)
        exit() # 마지막 도달 종료조건
    if visited[now]!=0: #해당 이미 queen 있을 경우
        queen(now+1)
    else: # 해당 행에 퀸이 없을 경우 
        for i in range(n+1):
            if i in visited or (now+i) in diag1 or (now-i)  in diag2: #가지치기 조건
                continue # 같은 열에 퀸이 존재여부, 왼쪽대각선, 오른쪽 대각선 퀸 여부
            diag1.add(now+i) # 왼쪽 대각선 추가
            diag2.add(now-i) # 오른쪽 대각선 추가 
            visited[now]=i # 열에 퀸 위치 추가 
            queen(now+1) # 재귀함수 시행 종료 후 입력 조건 철회
            visited[now]=0
            diag1.remove(now+i)
            diag2.remove(now-i)
        
queen(0)
print(-1)

 

대각선 퀸 체크는 set을 통해 조회하여 O(n)의 시간복잡도를 가지게하여 퀸의 같은 열에 존재 여부, 대각선  존재 여부를 기준으로 가지치기하여 문제를 해결하였다.