[알고리즘/파이썬] 백트래킹

ryun·2023년 3월 22일
0

알고리즘

목록 보기
1/2
post-thumbnail

📍 백트래킹

해결책에 대한 후보를 구축하다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙 Backtrack)해 정답을 찾아가는 범용적인 알고리즘


DFS와 백트래킹의 관계

DFS와 짝꿍처럼 등장하지만 백트래킹은 DFS보다 더 광의의 의미를 지닌다

  • DFS는 백트래킹의 골격을 이루는 알고리즘
  • DFS는 끝에 도달할 때까지 계속 탐색한다
  • 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻하지만 DFS와 다르게 불필요한 탐색은 하지 않는다

백트래킹 특징

  • 미로찾기 문제 등에서 유용하게 사용할 수 있다
  • 운이 좋으면 빠르게 목적지에 도착할 수 있지만 최악의 경우에는 모든 경우를 다 거친 다음에 도착할 수 있다 (결국 부르트포스)
  • 재귀로 접근하는 것이 편하다
부르트 포스로 전체 탐색을 시도하는 경우 백트래킹으로 가지치기를 한 경우엔 탐색이 훨씬 최적화 된다

문제

백준 N과 M (1)
https://www.acmicpc.net/problem/15649

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력

def permutation(n, lst):
    # 종료 조건 + 정답 처리
    if n == M:
        result.append(lst)
        return

    # 하부 함수 호출
    for i in range(1, N+1):
        if visited[i] == 0: # 선택 안한 경우
            visited[i] = 1
            permutation(n + 1, lst+[i])
            visited[i] = 0

# (1 ≤ M ≤ N ≤ 8)
N, M = map(int, (input().split()))
result = [] # 정답 저장용
visited = [0] * (N + 1) # 중복 확인용

permutation(0, [])
for lst in result:
    print(*lst)

백트래킹 조건에 의해 아직 방문하지 않은 경우에만 방문하여 수열을 구한다!


0개의 댓글