백트래킹 (BackTracking)

DFS와 BFS알고리즘과 함께 가장 많이 언급되는 알고리즘은 BackTracking이다. BackTracking은 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 이와 관련해서 자세한 예시는 아래 블로그를 참조하자.

https://blog.encrypted.gg/732

[실전 알고리즘] 0x07강 - 백트래킹, 시뮬레이션_구버전

미연시를 예시로 들었는데 아주 이해가 잘된다. 백트래킹은 개념이 어렵다기보다는 구현이 어려운 알고리즘이다. 개념은 위에 간략하게 소개하긴 했지만, 개념을 한번 정리해보자. 

 

백트래킹

• 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기해 정답을 찾아가는 범용적인 알고리즘
• 탐색을 할 때 이 길이 아니다 싶으면 바로 이전 save point로 돌아가서 탐색을 다시 진행하는 형태
• 백트래킹은 재귀로 보통 구현하는데, 재귀 함수가 호출되고 조건에 맞지 않으면 종료되고 그전에 호출된 재귀로 돌아오므로, 백트래킹에서 말하는 '가능성이 없으면 후보를 포기해 정답을 찾아가는(다시 왔던 길로 돌아가는) 느낌이라고 할 수 있겠다.
• 안 되는 조건은 없애면서 탐색하기 때문에 시간 복잡도가 선형적으로 증가할 법한 문제에서 백트래킹을 적용하면 시간 복잡도를 줄일 수 있다.

개념은 위와 같다. 구현이 어려운 이유는 위 개념에서 나오듯이 빠져나와야 하는 savepoint를 설정해두고 이를 바탕으로 코드를 구현해야 하기 때문이다. 백문이 불여일견, 문제를 풀면서 백트래킹을 알아보자. 

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

15649번: N과 M (1)

백트래킹에서 거의 교과서와 같은 문제이다. 사실 백트래킹 구현을 하나도 해보지 않고 이 문제를 푸는 것은 너무나도 어렵다. 그러니 차근차근 구현해보자.

 

a,b = map(int,input().split())			#a,b 범위 입력
s=[]						#배열 초기화
def dfs():
    if len(s)==b:				#만약 길이같으면 출력
        print(' '.join(map(str,s)))
        return
    for i in range(1,a+1):			#1부터 차근차근 넣어준다.
    	if i not in s:				#만약 배열안에 i 가 있다면 넣어주지 않는다.
            s.append(i)				#추가
            dfs()				#다음을 추가해주기 위해 재귀 실행
            s.pop()				#재귀가 끝나면 그 다음수가 없는 것이므로 하나를 빼준다
dfs()

말로 설명하기보다 코드를 짜는 게 더 효율적이라 생각하여 코드를 적어줬다. 여기서 for문안에 dfs()가 하나 더 들어가 있는 부분이 가장 중요한 것 같다. 재귀로 되어있는 부분이며 가지치기라고도 부른다. 이 부분 덕분에 다음 인덱스가 없으면 돌아와서 다시 배열 추가를 해줄 수 있다. save point를 지정하는 것이다. 

 

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

9663번: N-Queen

이번에도 백준에서 유명하다 하는 백트래킹 문제인 n-queen을 풀어보자. 사실 이 문제는 처음에 브루트 포스로 문제를 푸려다 번번이 시간 초과에 막혀서 구글의 도움을 받아 백트래킹으로 풀어보았다. 우선 이 문제 역시 위에서 언급한 백트래킹 강의에서 잘 가르쳐준다. 풀이를 생각해보자. 우선 결론적인 얘기지만, 체스의 말들이 놓일 배열이 2차원 리스트일 필요는 없다. 처음에 2차원 리스트로 풀었다가, 너무 어려워져서 구글에게 물어보니 1차원 리스트로 해도 충분히 구현이 가능하다는 것을 보여줬다. 단순하게 1차원 리스트의 각 인덱스가 그 행의 몇 번째 열에 놓여있다 라는 것을 생각하면 된다. 예를 들어 row = [1,3,2]라는 배열이 있다고 가정하자 그러면 체스 말들은

Chess
		Chess
	Chess

위와 같이 놓여져 있는 것이다. 첫 번째 인덱스는 첫 번째 행의 위치정보, 두 번째 인덱스는 두 번째 행의 위치정보를 담고 있게 되는 것이다. 그러고 나서 백트래킹으로 문제를 생각해보자.

일단 0번째 행부터 0번 자리에 놓고 그 행에는 더 이상 놓을 수 없으므로 다음행에 놓게 하자. 그러고 나서 다음행 첫 번째 열부터 체스 말을 놔준 다음에, 배열을 보내어 말들의 위치가 주어진 조건을 만족하는지 확인해보자. 여기서 확인 알고리즘은 간단하다. 그냥 row의 모든 행들 중에 같은 값이 있으면 false를 출력하게 하고, 대각선에 위치했는지 조사하기 위해서 row의 값들과 인덱스의 값들을 뺀 것들을 각각 절댓값 한 것들이 같으면 대각선에 위치한 것이기 때문에 false를 반환한다. 그리고 문제없이 for문을 나오게 되면 true를 반환하도록 check 함수를 설계한다. 만약 문제없이 true가 나왔다면 말 들은 잘 놓인 것이기 때문에 다음 행에 말을 놔야 한다. 그렇기 때문에 재귀로 다음 말을 실행하면 된다.

n = int(input())
row = [0]*n
ans = 0
def check(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x]-row[i])==abs(x-i):
            return False

    return True

def dfs(x):
    global ans
    if x==n:
        ans+=1
    else:
        for i in range(n):
            row[x] = i
            if check(x):
                dfs(x+1)
dfs(0)
print(ans)

코드로 짜면 위와 같이 나온다. 사실 코드만 놓고 보면 어려울 것이 없다. 하지만, 이런 생각을 했다는 것이 대단한 것 같다. 그렇게 코드를 짜주고 룰루랄라 실행을 시켜봤는데 시간 초과가 계속 났다... 이 역시 구선생님에게 여쭤보니 특정 조건이 더 추가된 것 같다고, 새로운 코드를 만들어 줘야 할 것 같다고 하셨다. 그러다 번뜩 학교 선배의 C++도 활용해보라는 말이 떠올랐다. 파이썬의 알고리즘을 그대로 C++로 만들어주면, 훨씬 좋은 효율을 보일 수 있다는 말이 떠올랐다. C++은 잘 모르지만 알고리즘은 다 짰기 때문에 그냥 기능들만 C++로 짜주었다. 

#include <iostream>

using namespace std;
int n, ans = 0;
int row[15];

bool check(int j){
    for (int i = 0; i<j; i++){
        if(row[j] ==row[i] || abs(row[j] - row[i]) == abs(j-i)){
            return false;
        }
    }
    return true;
}

void dfs(int x){
    if (x==n)
    {
        ans++;
    }
    else
    {
        for(int i = 0; i<n; i++){
            row[x] = i;
            if (check(x)){
                dfs(x+1);
            }
        }
    }
}
int main(){
    cin >> n;
    dfs(0);
    cout << ans;
}

코드짜는 시간보다 세팅하는 시간이 더 오래 걸렸다.