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

---

☑️ 백트래킹(Backtracking)

해를 찾다가 더 이상 진행할 수 없으면, 다시 뒤로(Back) 돌아가서 해를 찾는 방법을 의미한다.
수학과 친하지 않기 때문에 다른 방식으로 설명하면 모든 조합의 수를 탐색하지만, 조건이 맞는 경우만 탐색한다.
조건에 부합하지 않으면 제외한다.

 

 

☑️ DFS / BFS랑은 무슨 관계인가?

백트래킹에 관련된 키워드로 DFS와 BFS를 들을 수 있다. 백트래킹 알고리즘은 DFS와 BFS 알고리즘과 무슨 관계에 있을까? 별 것 없다. DFS와 BFS 알고리즘을 통해서 백트래킹을 구현할 수 있다. 백트래킹은 일종의 추상적인 개념과 같다면, DFS와 BFS는 추상적인 개념을 기법으로 정의해둔 것이다. 우리가 여기까지 알았다면 이제 이렇게 말할 수 있다.

아! 백트래킹 문제니까 DFS나 BFS 중에서 선택하면 되겠구나!

 

정리해보면, 백트래킹은 문제 해결 전략을 의미하고 DFS와 BFS는 그것을 구현하는 기술적인 정의를 말하는 것이다. 그런데 또, 재미있는건 DFS와 BFS가 백트래킹 자체를 의미하는 것은 아니다. DFS / BFS는 완전 탐색 기법으로 불린다. 나중에 정리하겠지만 지금은 백트래킹을 DFS와 BFS를 통해서 구현할 수 있구나! 정도로 생각해두자.

 

☑️ 백트래킹의 가지치기(Pruning)

백트래킹은 모든 조합의 수를 탐색한다. 여기까지라면 완전 탐색 기법과 동일하다. 하지만, 앞에 말한 것과 같이 백트래킹은 조건이 맞지 않는 조합의 수는 탐색을 진행하지 않는다. 조건에 필요 없는 부분은 버린다. 이러한 행위의 이름을 가지치기라 한다.

 

🔍 왜 가지치기를 해야하죠?

첫번째 이유이자, 가장 핵심적인 사유로 불필요한 탐색을 줄임으로서 메모리 공간 사용량을 줄일 수 있다. 필요하지 않은 경로에 대해서 탐색할 필요가 없다면 탐색하지 않으면 된다. 그만큼의 메모리 공간과 시간을 지킬 수 있다.

 

☑️ 백트래킹의 예제 코드(Python)

// 나무위키
def dfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다.
    visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다.
    def search(current:int): # 재귀함수 정의
        visited[current] = True # current 방문
        for nxt in graph[current]: # current의 인접 노드를 확인한다. 이 노드를 nxt라고 하자.
            if not visited[nxt]: # 만일 nxt에 방문하지 않았다면
                search(nxt) #nxt 방문
    search(start)

 

📜 추천 문제

풀어본 문제 중에서 DFS를 사용하는 문제로 유명한 N-Queen을 추천한다. 참고로 정말 많이 실패하고 성공했다... 다들 포기하지 말고 화이팅

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