Algorithm - [ 백트래킹 ]

백트래킹

그리디와 백트래킹의 차이

• 그리디 알고리즘
• 각 단계에서 가장 유리한 선택을 하는 것을 반복하면서 지역적으로 최적해를 구한다.
• 최적해에 도달하지 못하는 경우와 같이 최적해를 보장하지는 않을 수 있지만, 빠른 솔루션을 제공한다.
• 그리디 알고리즘은 최적 부분 구조와 탐욕 선택 속성을 가진 문제에 적용된다.

• 백트래킹 알고리즘
• 일반적으로 DFS 를 기반으로 하는 재귀 함수를 주로 사용하여 모든 가능한 조합을 탐색하며, 유효한 상황은 계속 진행하고 유효하지 않은 상황에서는 이전 단계로 되돌아가서 다른 선택을 시도한다.
• 백트래킹 알고리즘은 모든 가능한 경우를 고려하기 때문에 일반적으로 더 많은 시간과 계산 자원을 요구한다.
• 백트래킹 알고리즘은 일반적으로 모든 해를 찾거나 특정 조건에 맞는 해를 찾을 때 사용된다.

백트래킹 알고리즘 구조

1. 원소 넣기

2. 재귀 호출

3. 원소 빼기

경우의 수

1. 순열: itertools.permutation()
N개의 원소 리스트에서 중복 없이 M개를 골라 만든 수열
N개에서 M개를 고르기 (순서가 다르면 다른 경우)

2. 조합: itertools.combination()
N개의 원소 리스트에서 중복 없이 M개를 골라 만든 수열
순서가 달라도 원소가 동일하면 같은 경우

3. 중복 순열: itertools.product()
N개의 원소 리스트 중에서 중복을 허용해서 M개를 골라 만든 수열
N개에서 M개를 고르기 (순서가 다르면 다른 경우)

4. 중복 조합: itertools.combinations_with_replacement()
N개의 원소 리스트에서 중복을 허용해서 M개를 골라 만든 수열
순서가 달라도 원소가 동일하면 같은 경우

1. 백트래킹 → 순열
순열 문제

# 순열
import sys
sys.setrecursionlimit(int(1e6))

n, m = map(int, input().split())
arr = [i for i in range(1, n + 1)]
visited = [False] * n  # 각 원소가 선택되었는가

selected = [] # 현재 경우에서 선택된 원소들

# depth: 현재 재귀에서 선택된 원소의 개수
def dfs(depth):
    if depth == m:
        # 실제로 현재 경우에 대하여 처리하는 부분
        for x in selected:
            print(x, end=" ")
        print()
        return

    for i in range(n):
        if visited[i]:
            continue
        # 백트래킹의 재귀 호출 3단계
        # (1) 원소 넣기
        selected.append(arr[i])
        visited[i] = True
        # (2) 재귀 호출
        dfs(depth + 1)
        # (3) 원소 빼기
        selected.pop()
        visited[i] = False

dfs(0)

참고: return 문만 사용하여 함수를 종료하는 경우에는 값을 반환하지 않고, 단순히 함수의 실행을 종료한다. 이는 주로 재귀 함수에서 탈출 조건을 만족할 때 함수를 종료하고 이전 단계로 돌아가는 용도로 사용된다.
 

2. 백트래킹 → 조합
조합 문제

# 조합
import sys
sys.setrecursionlimit(int(1e6))

n, m = map(int, input().split())
arr = [i for i in range(1, n + 1)]
visited = [False] * n # 각 원소가 선택되었는가

selected = [] # 현재 경우에서 선택된 원소들

# depth: 현재 재귀에서 선택된 원소의 개수
def dfs(depth, now):
    if depth == m:
        # 실제로 현재 경우에 대하여 처리하는 부분
        for x in selected:
            print(x, end=" ")
        print()
        return

    for i in range(now, n):
        if visited[i]:
            continue
        # 백트래킹의 재귀 호출 3단계
        # (1) 원소 넣기
        selected.append(arr[i])
        visited[i] = True
        # (2) 재귀 호출
        dfs(depth + 1, i)
        # (3) 원소 빼기
        selected.pop()
        visited[i] = False

dfs(0, 0)

순열과 달리 조합은 [1, 2, 3, 4, 5]가 있을 때, [1, 2, 4], [1, 2, 5]를 골랐다면 [1, 4, 2], [1, 5, 2]도 고르는 게 안 된다.
⇒ 따라서 현재보다 큰 인덱스만 고를 수 있도록 파라미터에 now 추가
 

3. 백트래킹 → 중복 순열
중복 순열 문제

# 중복 순열
import sys
sys.setrecursionlimit(int(1e6))

n, m = map(int, input().split())
arr = [i for i in range(1, n + 1)]
# visited = [False] * n # 각 원소가 선택되었는가

selected = [] # 현재 경우에서 선택된 원소들

# depth: 현재 재귀에서 선택된 원소의 개수
def dfs(depth):
    if depth == m:
        # 실제로 현재 경우에 대하여 처리하는 부분
        for x in selected:
            print(x, end=" ")
        print()
        return

    for i in range(n):
        # if visited[i]:
            # continue
        # 백트래킹의 재귀 호출 3단계
        # (1) 원소 넣기
        selected.append(arr[i])
        # visited[i] = True
				# (2) 재귀 호출
        dfs(depth + 1)
        # (3) 원소 빼기
        selected.pop()
        # visited[i] = False

dfs(0)

중복 순열은 순열에서 방문 처리만 없으면 된다.
 

4. 백트래킹 → 중복 조합
중복 조합 문제

import sys
sys.setrecursionlimit(int(1e6))

n, m = map(int, input().split())
arr = [i for i in range(1, n + 1)]
# visited = [False] * n  # 각 원소가 선택되었는가

selected = []  # 현재 경우에서 선택된 원소들

# depth: 현재 재귀에서 선택된 원소의 개수
def dfs(depth, now):
    if depth == m:
        # 실제로 현재 경우에 대하여 처리하는 부분
        for x in selected:
            print(x, end=" ")
        print()
        return
    
    for i in range(now, n):
        # if visited[i]:
            # continue
        # 백트래킹의 재귀 호출 3단계
        # (1) 원소 넣기
        selected.append(arr[i])
        # visited[i] = True
        # (2) 재귀 호출
        dfs(depth + 1, i)
        # (3) 원소 빼기
        selected.pop()
        # visited[i] = False

dfs(0, 0)

중복 조합은 조합에서 방문 처리만 없으면 된다.