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

🌵백트래킹 알고리즘이란?

모든 경우의 수를 전부 고려하는 알고리즘이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다.
방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다.

즉, 백트래킹은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다가 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘이다.

 

• DFS의 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다.
• 백트래킹은 가지치기(Purning)을 통해 효율을 극대화한다.
• Purning : 가능성이 없는 루트를 가지치기로 쳐내서 탐색하는 기법
• Promising : 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.

 

 

 

🌵 백트래킹 구현방법

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

 

 

 

🌵DFS와의 차이

 

'가능한 모든 방법을 탐색한다'라는 의미에서 깊이 우선 탐색법인 DFS와 유사하지만,

백트래킹은 경로 탐색 중 유망하지 않은 (Not Promising) 경로가 나오게 되면 더 이상 탐색하지 않고 가지치기를 하고, 그 전 단계로 Back 한다.

 

 

---

 

🌵 파이썬에서의 백트래킹 구현 - itertools 내장함수 사용

백트래킹 알고리즘을 직접 구현할 수도 있지만, 파이썬에서는 라이브러리를 이용해 백트래킹을 쉽게 사용할 수 있다.

 

 

🎯import itertools

: 효율적인 루핑을 위한 이터레이터를 만드는 함수

*  입력 iterable의 순서에 따라 사전식 순서로 방출.

* 따라서, 입력 iterable이 정렬되어있으면, 조합 튜플이 정렬된 순서로 생성

 

다양한 내장함수들 가운데 조합 / 순열을 구현하는 함수들을 살펴보자.

조합 / 순열의 개념은 아래에서 확인할 수 있다.

https://gyurisinzorba.tistory.com/m/29 

[Algorithm] 순열 및 조합 공식 정리

 

 

1. combinations(iterable, r) : iterable에서 원소 개수가 r개인 조합 추출

 

# 조합 : 중복을 고려하지 않고 순서 존재

from itertools import combinations

l = [1,2,3,4]

for i in combinations(l,2):
    print(i)

 

🚀결과

 

🚀관련문제 

[백준 알고리즘 15650번: N과 M (2)]

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

🎯코드

import itertools
n, m = map(int,input().split())
num_list = [i for i in range(1,n+1)]

arr = itertools.combinations(num_list, m)

for i in arr:
    for j in i:
        print(j, end=' ')
    print()

 

 

 

2. combinations_with_replacement(iterable, r) : iterable에서 원소 개수가 r개인 중복 조합 추출

 

# 중복 조합 : 중복을 허용하고 순서 존재

from itertools import combinations_with_replacement

l = [1,2,3,4]

for i in combinations_with_replacement(l,2):
    print(i)

 

🚀결과

🚀관련 문제

[백준 알고리즘 15652번 : N과 M (4)]

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

🎯코드

import itertools
n, m = map(int,input().split())
num_list = [i for i in range(1,n+1)]

arr = itertools.combinations_with_replacement(num_list, m)

for i in arr:
    for j in i:
        print(j, end=' ')
    print()

 

 

 

3. permutations(iterable, r = None) : iterable에서 원소 개수가 r개인 순열 추출

 

# 순열 : 중복을 허용하지 않고 순서도 존재하지 않음

from itertools import permutations

l = [1,2,3,4]

for i in permutations(l,2):
    print(i)

 

🚀결과

🚀관련문제 

[백준 알고리즘 15649번 : N과 M(1)]

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

🎯코드

 

import itertools

n, m = map(int, input().split())
nums = [i for i in range(1, n+1)]

array = itertools.permutations(nums, m)

for i in array:
    for j in i:
        print(j, end = ' ')
    print()

 

 

 

4. product(*iterables, repeat = 1) : 여러 iterable의 데카르트 곱 리턴

 

# 중복 순열 : 중복을 허용하고 순서는 고려하지 않음

from itertools import product
l = [1,2,3,4]

for i in product(l,repeat = 2):
    print(i)

 

🚀결과

🚀관련문제 

[백준 알고리즘 15651번 : N과 M (3)]

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

🎯코드

import itertools
n, m = map(int,input().split())
num_list = [i for i in range(1,n+1)]

arr = itertools.product(num_list, repeat=m)

for i in arr:
    for j in i:
        print(j, end=' ')
    print()

 

 

 

🌵 파이썬에서의 백트래킹 구현 - 재귀함수 사용

• 재귀 함수의 종료 시점 부터 지정
• 주로 종료 시점 이후부터 for 반복문이 등장
• for문 안에 각각의 경우에 대해 값을 바꿔가며 재귀함수를 호출
• 시간 초과를 막기 위해 모든 for문을 돌지 않고, 특정 경우에만 실행하도록 가지치기

def backtracking(loc, ...):
    # 종료를 위한 조건문
    if ... :
        return
    
    # 현재 위치분터 for문
    for i in range(loc, ...):
        backtracking(i+1, ...)
    return

 

 

 

 

🌵관련문제

🥈[백준 알고리즘 : N과 M 시리즈 ]

 

[SOLUTION]

 

 

---

 

🥈[백준 알고리즘 14888번 : 연산자 끼워넣기]

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

[SOLUTION]

 

 

 

---

 

~ 해당 포스팅은 업데이트 중 ~