[알고리즘] 백트래킹 (Backtracking)

출처:  baaarkingDog님 유튜브

[바킹독의 실전 알고리즘] 내용을 기반으로 정리한 포스팅입니다.

---

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

현재 상태에서 가능한 모든 선택지를 다 플레이해보는 방법

 

가능한 상태에 대한 트리로 생각할 수 있다.

• 백트래킹은 상태를 넘나든다.

def solution(k):  # 현재 k개까지 수를 택했음.
    if k == m:  # m개를 모두 택했으면
        for i in range(m):
            print(temp[i], end=' ')  # temp에 기록해둔 수를 출력
        print()
        return

    for i in range(1, n + 1):  # 1부터 n까지의 수에 대해
        if not visited[i]:  # 아직 i가 사용되지 않았으면
            temp[k] = i  # k번째 수를 i로 정함
            visited[i] = True  # i를 사용되었다고 표시
            solution(k + 1)  # 다음 수를 정하러 한 단계 더 들어감
            visited[i] = False  # k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지 않았다고 명시함.


n, m = map(int, input().split())
temp = [0] * 10
visited = [False] * 10
solution(0)

• 위는 1부터 n까지의 수에서 m개의 원소로 이루어진 가능한 조합의 경우를 구하는 문제.
• 다음과 같은 예제에서, k번째 선택 수에 따라 가능한 상태 조합이 달라진다. 

상태 공간 트리를 탐색 및 체크

 

Check-in, Check-out의 아이디어

• '이' 경우 해당하는 상태가 쓰였다고 체크하는 것이 체크인
• 해당 경우의 수가 끝난 이후에 다른 경우의 수에서 사용할 수 있도록 원상복구 해주는 것이 체크아웃
• 백트래킹에서 만족하지 않는 경우의 수에 대해서는 빨리 프루닝 해야하므로 체크아웃 잘 해줘야 한다.

for i in range(1, n + 1): 
    if not visited[i]: 
        # ...
        visited[i] = True  # check-in
        solution(k + 1)  # 다음 수를 정하러 한 단계 더 들어감
        visited[i] = False  # check-out

 

 

프루닝

• 가지치기가 빈번하면 시간 복잡도 측정하기 어려움
• 최적화할 수 있는 부분 찾아서 최적화 후 릴리즈

 

상태공간트리 생각하기

• 예시: 부분 수열의 합

• 매 순간 뭘 선택할지 고민 (현재 수를 부분수열에 추가할지, 추가하지 않을지 분기)
• 현재(curr) 어디 위치인지 기록하기 (반복되는 위치 k or curr)
• 현재(curr) 상태를 기록해도 좋음 (sum, 쌓아온 알파벳, 쌓여온 로드 등)

 

예시 문제들

🚀 예제 문제 및 해결

✔︎ BOJ 15649번 N과 M (1)

def solution(k):  # 현재 k개까지 수를 택했음.
    if k == m:  # m개를 모두 택했으면
        for i in range(m):
            print(temp[i], end=' ')  # temp에 기록해둔 수를 출력
        print()
        return

    for i in range(1, n + 1):  # 1부터 n까지의 수에 대해
        if visited[i]:  # 사용되었으면 continue
            continue
        temp[k] = i  # k번째 수를 i로 정함
        visited[i] = True  # i를 사용되었다고 표시
        solution(k + 1)  # 다음 수를 정하러 한 단계 더 들어감
        visited[i] = False  # k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지 않았다고 명시함.


n, m = map(int, input().split())
temp = [0] * 10
visited = [False] * 10
solution(0)

 

 

✔︎ BOJ 9663번 N-Queen

• 체크인과 체크아웃의 아이디어를 이용한 풀이

def solution(n, curr):
    global cnt
    if curr == n:
        cnt += 1
        return
    for i in range(n):
        # 열마다 살펴봄, 같은 열 / 왼쪽 대각 / 오른 대각 유효한 자리인지 검증
        if visited1[i] or visited2[curr + i] or visited3[curr - i + n - 1]:
            continue
        # check-in
        visited1[i] = True
        visited2[curr + i] = True
        visited3[curr - i + n - 1] = True
        # recursion
        solution(n, curr + 1)
        # check-out
        visited1[i] = False
        visited2[curr + i] = False
        visited3[curr - i + n - 1] = False


N = int(input())
cnt = 0
visited1 = [False] * N * 2
visited2 = [False] * N * 2
visited3 = [False] * N * 2
solution(N, 0)

print(cnt)

 

• 또 다른 풀이: abs(row - col) == abs(queens[row] - queens[col])인 케이스로 대각 체크를 하는 경우

n = int(input())
cnt = 0

def is_valid_position(row, queens):
    for col in range(row):
        # 세로 체크
        if queens[col] == queens[row]:
            return False
        # 대각선 체크
        if abs(row - col) == abs(queens[row] - queens[col]):
            return False
    return True

def put_queen(row, queens):
    global cnt
    if row == n:
        cnt += 1
        return
    
    for col in range(n):
        queens[row] = col
        if is_valid_position(row, queens):
            put_queen(row + 1, queens)

def solution():
    queens = [0] * n
    put_queen(0, queens)
    return cnt

print(solution())

 

 

✔︎ BOJ 1182번 부분 수열의 합

• 현재 보고 있는 인덱스의 숫자를 포함하는지 포함하지 않는지 (두 가지 경우)로 상태를 나눠 재귀 

이 이미지와 같다.

N, S = map(int, input().split())
cnt = 0
arr = list(map(int, input().split()))


def solution(curr, curr_sum):
    global cnt, N, S
    if curr == N:
        if curr_sum == S:
            cnt += 1
        return
    solution(curr + 1, curr_sum)
    solution(curr + 1, curr_sum + arr[curr])


solution(0, 0)
if S == 0:
    cnt -= 1
print(cnt)

 

 

---

출처:  baaarkingDog님 유튜브

[바킹독의 실전 알고리즘] 내용을 기반으로 정리한 포스팅입니다.