[알고리즘] Backtracking : 여기가 아닌가? 돌아가자

이 방법이 아닌가봐!!!

1. 백트래킹이란?

• 정의 및 개념: 백트래킹은 재귀적으로 가능한 모든 해를 탐색하는 알고리즘 기법입니다.

이게 아니야 하면 생각나는 '독짓는 늙은이'의 한 구절...

• 백트래킹의 기본 원리: 조건을 만족하지 않는 경우 이전 단계로 돌아가 다른 경로를 탐색하는 방식으로 동작합니다. 쉽게 말하면 전부 다~ 해보고 고민하는 것입니다.
• 백트래킹의 활용 예시: 퍼즐 해결, 조합, 순열, 그래프 탐색 등 다양한 문제에 사용됩니다. 재귀는 사용할 수 만 있다면 정말 좋은 풀이법이기에 시간초과만 해당하지 않는다면 우선순위로 둬야할 풀이법입니다.

2. 백트래킹의 주요 개념

• 문제 분할 (Problem Division): 문제를 작은 부분 문제로 나누어 해결합니다.
• 조건 검증 (Constraint Verification): 현재 상태가 조건을 만족하는지 확인합니다.
• 해결 및 해 확인 (Solution and Validation): 목표 조건에 도달하면 해를 찾은 것으로 간주합니다.
• 되돌아가기 (Backtracking): 모든 가능한 선택을 시도한 후 선택을 취소하고 이전 상태로 돌아갑니다.
• 이렇게 잘 정리되어 있는 경우는 이해하기는 편하지만 실제로 사용할 때는 일단 큰 수에서 줄여보는 생각으로 시작하는 게 그나마 풀이를 얻는 게 좋은 듯 합니다.

3. 백트래킹의 구조

• 백트래킹 알고리즘의 기본 구조: 재귀 함수 형태로 작성되며, 종료 조건과 재귀 호출이 포함됩니다.
• 재귀적 호출과 가지치기: 재귀적으로 호출하면서 불필요한 경로를 가지치기(pruning)하여 효율성을 높입니다.

def backtrack(현재 상태, 선택지):
    if 종료 조건:
        해를 찾았으므로 기록 또는 반환
    else:
        for 선택 in 선택지:
            현재 선택이 유효한지 확인
            if 유효하다면:
                선택을 상태에 반영
                backtrack(갱신된 상태, 선택지)
                상태를 이전으로 복원

4. 백트래킹의 예제

밑의 예제는 매우 유사한 문제끼리 얽혀있어서 백트랙킹을 연습하는 용도로 좋은 문제들입니다.

4-1. 백준 문제 15649번 "N과 M (1)"

• 문제 설명: 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제입니다.
• 문제 접근 방법: 백트래킹을 사용하여 가능한 모든 수열을 생성합니다.
• 예제 코드 및 설명: 문제를 해결하는 백트래킹 코드와 그 동작 원리를 설명합니다.

4-2. 백준 문제 15650번 "N과 M (2)"

• 문제 설명: 1부터 N까지의 자연수 중에서 중복 없이 M개를 고르고, 오름차순으로 정렬된 수열을 구하는 문제입니다.
• 문제 접근 방법: 백트래킹을 사용하여 가능한 모든 오름차순 수열을 생성합니다.
• 예제 코드 및 설명: 문제를 해결하는 백트래킹 코드와 그 동작 원리를 설명합니다.

4-3. 백준 문제 18290번 "NM과 K (1)"

• 문제 설명: 주어진 N x M 격자에서 K개의 칸을 선택하여 합이 최대가 되도록 하는 문제입니다. 단, 선택한 칸이 인접하면 안 됩니다.
• 문제 접근 방법: 백트래킹을 사용하여 가능한 모든 조합을 탐색하면서 조건을 만족하는 경우만 선택합니다.
• 예제 코드 및 설명: 문제를 해결하는 백트래킹 코드와 그 동작 원리를 설명합니다.

5. 백트래킹의 응용 분야

• 퍼즐 해결: 스도쿠, 미로 찾기 등 다양한 퍼즐 문제 해결에 사용됩니다.
• 그래프 탐색: DFS와 같은 그래프 탐색 알고리즘에 백트래킹이 사용됩니다.
• 조합 및 순열 문제: 모든 가능한 조합과 순열을 탐색하는 문제에 사용됩니다.

6. 결론

• 백트래킹의 장점과 단점: 모든 가능한 해를 탐색할 수 있는 장점도 있으나 탐색 공간이 큰 경우 비효율적일 수 있는 단점 역시 존재합니다. 그래서 문제의 조건이 굉장히 작은 수일 경우 백트랙킹, 즉 재귀를 사용해서 해결 가능한지 확인해봐야합니다.