[algo] 백트래킹(Backtracking)이란?

letsbebrave·2022년 4월 5일

DFS 백트래킹 알고리즘 코딩테스트

algorithm

목록 보기

3/16

백트래킹 (Backtracking)

aka. 퇴각 검색 (Backtrack)
제약 조건 만족 문제에서 해를 찾기 위한 전략

해답이 될 수 있는 모든 벡터를 만들어 탐색하는 브루트포스는 시간과 공간의 복잡도가 증가하여 원하는 시간에 문제를 풀지 못하는 상황이 발생

해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보를 체크하지 않을 것을 표기)하고, 바로 다른 후보로 넘어가며, 결국 최적의 해를 찾는 방법

실제 구현시, 고려할 수 있는 모든 경우의 수 (후보)를 상태공간트리(State Space Tree)를 통해 표현

각 후보를 DFS 방식으로 확인

상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색

(위) 상태 공간 트리

Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법
즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리(나무)에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버림 (Pruning)

백트래킹 구현

해를 구하는 도중 해가 아니어서 막히면 막히기 전으로 다시 돌아가서 해를 찾는 기법
예를 들어, 갈랫길에서 한쪽으로 갔다가 이 길이 아닌 것 같으면 왔던 길로 되돌아와 다른 선택지로 간다고 생각하면 된다.
가상의 트리에서 해를 구하기 위해 부모 노드에서 자식 노드까지 뻗어나간다. 만약 해당 노드가 조건에 맞지 않는다면 다시 부모노드로 돌아간다.
해가 아닌 선택지는 없애면서 탐색하기 때문에 시간복잡도를 줄일 수 있다.

대표적인 백트래킹 문제

N-Queen

https://velog.io/@letsbebrave/백준-9663-N-Queen

import sys

n = int(sys.stdin.readline())
mlist=[0]*n

def check(mlist, row): # Promising : 해당 행에 원소 배치해도 되는지 검사
    for i in range(row):
        if mlist[i] == mlist[row] or abs(mlist[row]-mlist[i]) == row - i:
            return False # 방문할 수 없는 경우이므로 False 주기
    return True

def search(mlist, row):
    count = 0
    if n == row:
        return 1
    
    for col in range(n):
        mlist[row] = col
        if check(mlist, row): # 퀸들이 이동할 수 없을 경우엔 다음 컬렴 (백트래킹)
            count += search(mlist, row+1)
    
    return count

print(search(mlist, 0))

예시 1

[풀이]
1. 중복 방지를 위해 방문 여부를 알려주는 visited라는 리스트를 만들어서 숫자의 범위인 n만큼 False라는 값을 채워준다.
2. 결과를 담아서 출력해 줄 answer라는 빈 배열을 선언해준다.
3. depth, n, m을 입력받는데 이때, depth는 answer 배열에 들어온 숫자의 개수가 된다. depth가 m과 같아진다면 문제에서 요구하는 수열을 찾은 것이므로 출력하고 함수가 종료된다.
4. depth와 m이 같지 않다면 아직 탐색해야 할 숫자가 남았다는 의미이므로 visited에 False값이 저장되어 아직 방문하지 않은 숫자를 방문한다.
5. 방문한 숫자는 방문했다는 의미로 visited에 True를 저장해주고 depth를 1증가시킨 상태에서 재귀함수를 실행한다.
6. 함수를 다시 실행하면 금방 방문한 숫자를 answer배열에 저장하고 해당 함수에서 나오게 되면 방문했다는 표시를 다시 False로 바꿔주고 해당 숫자를 pop해주어야 원래 자리로 돌아가서 다음 탐색을 할 수 있게 된다.

def n_and_m(depth, n, m):

  if depth == m:
    print(' '.join(map(str, answer))) # 바로 프린트 해줬으므로 return을 딱히 안 한 것 같음

  for i in range(1, n+1):
    
    if not visited[i]:
      visited[i] = True
      answer.append(i)
      n_and_m(depth+1, n, m)
      visited[i] = False
      answer.pop()

n, m = map(int, input().split())
visited = [False] * (n+1)
answer = []

n_and_m(0, n, m)

예시 2

def make_wall(cnt):
    if cnt == 3:
        bfs()
        return  # 여기 리턴을 빼먹었음! 재귀가 종료되어야 다음 것이 실행 안되고 호출해 준 함수 다음 칸으로 다시 돌아갈 수 있음
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                make_wall(cnt + 1)
                graph[i][j] = 0  # 재귀 끝나고 돌아오면서 원래 호출한 cnt로 하나씩 차감되고 비로소 0이됨 & graph 값 0으로 다 바꿈

make_wall(0)