[알고리즘] 백트래킹 Backtracking

최근 코딩테스트 문제를 풀면서 알고리즘 정리가 필요함을 느꼈다.

자주 출제되는데 아직 나에게 어려운 백트래킹을 먼저 정리해보려고 한다.

 

---

백트래킹

 

모든 경우의 수를 고려하는 알고리즘

 

백트래킹은 재귀를 활용해 모든 경우의 수를 확인하는 알고리즘이다.

대표적으로 DFS, BFS를 사용하며 코딩테스트에서 잘 다루어지는 알고리즘이기도 하다.

시간복잡도는 중복이 가능한 경우, N**2이고 중복이 불가한 경우는 N!이다.

 

목표한 조건에 도달하는 경우를 탐색하는 것인데,

절대 목표에 도달할 수 없다고 판단이 되면 앞으로 돌아가서 다시 그 조건에 맞는 경우를 탐색한다.

 

1. DFS

깊이 우선 탐색

트리에서 바닥에 도달할 때까지 한쪽 방향으로만 내려가는 방식으로

재귀함수를 사용하여 목표한 바가 나올 때까지 반복한다.

일반적으로 모든 경우의 수를 고려해야 할 때는 DFS가 편리하다.

단, 루프가 있거나 분기점 없이 긴 길이 있다면 DFS가 불리하다.

 

2. BFS

너비 우선 탐색

모든 분기점을 다 검사하면서 진행하는 방식으로

큐를 써서 새로운 경우는 큐에 넣고 검사한 원소는 큐에서 뺀다.

DFS의 단점을 개선하기 위해 최단 거리 구하기에서 사용하면 좋다.

 

3. 최선 우선 탐색

우선순위 큐를 사용하여 구현하며 가장 효율적인 방법이다.

무의미한 탐색을 막기 위한 가지치기(Bounded function)가 있을 경우 성능이 향상된다.

 

4. 구현 팁

중복를 허용하지 않는 경우, visited 배열을 활용하여 방문 여부를 체크해야 한다.

재귀를 반복하다가 결과가 n개가 되면 return할 수 있도록 if문을 추가해야 한다.

 

5. 예시 문제

백준 15649번 N과 M(1)

 

대표적인 백트래킹 문제이다.

어떤 조건을 만족하는 것을 모두 구하는 문제이다.

순열 문제라고 생각할 수도 있을 것 같다.

permutations(arr, m)과 결과가 같겠지만!!

백트래킹 적용을 위해 DFS를 사용하여 구현해보겠다.

 

def dfs():
    #만약 원하는 길이가 된 경우 출력하고 return
    if len(s) == m: 
        print(' '.join(map(str, s)))
        return
    #1부터 n까지 배열 안에 없는 경우 추가하고 dfs 실행 후 삭제함
    for i in range(1, n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()

#입력 받기
n, m = map(int, input().split())
s = [] #가능한 배열
dfs()

 

원하는 길이가 되기 전까지 배열 안에 해당 차례의 숫자가 없는 경우에는 추가하고

dfs를 실행한 뒤에 다시 배열에서 그 숫자를 빼주는 방식이다.

 

예를 들어 n = 3, m = 2인 경우에, 반복문을 돌리면

i = 1일 때 s 안에 아무것도 없으므로 일단 1을 추가하고 dfs를 실행한다.

dfs가 시작되면 아직 len(s)가 1이므로 아래 반복문으로 다시 넘어간다.

i = 1일 때 이미 s 안에 있으므로 조건문이 실행되지 않고,

i = 2로 넘어가서 s 안에 2가 없으므로 2를 추가하고 다시 dfs를 실행한다.

len(s)가 2이므로 s값을 출력하고 return 하여 이전 상황으로 돌아간다.

이때 s = [1, 2]이므로 s.pop()을 통해 가장 뒤에 넣었던 2를 제거해준다.

다음 반복문을 돌면 3도 마찬가지의 과정을 거쳐 s = [1, 3]이 출력된다.

 

---

 

N과 M 시리즈가 백준에 여러 문제가 있어서 다른 문제들도 풀어보면서

백트래킹을 확실히 학습해야겠다.