백트래킹 알고리즘 (Back Tracking)

  다음과 같은 그래프가 있다.

여기서 1부터 시작해서 숫자 순서대로 얼마나 멀리 갈 수 있는지 찾고싶다. 즉 1->2->3->4->5->... 이런식의 루트를 찾으려 한다.

 

 

  우선 생각해볼 수 있는 방법은, 그냥 모든 루트에 대해 DFS 등을 사용해 전부 탐색해 보는 것이다. 이 방식이 이전에 작성한 Brute Force 방식이다. 그냥 컴퓨터의 빠른 연산력에 기대어 모든 경우를 확인하는 것이다.

위는 모든 경우를 살펴보는 DFS 과정의 순서를 표시한 것이다. 모든 경우를 확인해보니 결국 1->2->3->4를 찾긴했다.

 

 

  그런데 우린 직관적으로, 중간과정에서 이미 순서가 안맞다면 해당 루트로는 아예 안가봐도 될 것임을 알 수 있다. 그럼 다음 이미지를 보자.

위와 같이 답이 될 가능성이 없는 경로라면 더이상 살펴볼 이유 자체가 없다. 위 이미지를 순서대로 말로 설명하면 다음과 같다.

 

순서1 : 진행해보니 '3'이 있다.

순서2 : 1->3은 그 뒤에 무엇이 있던 순서대로 진행이 불가하므로 되돌아간다. (Back)

순서3 : 다른 길로 다시 진행한다. (Tracking) 1->2 이므로 만족하는 경우이다. 계속 진행해본다.

순서4 : 1->2->4가 되었다.

순서5 : 찾는 경우가 아니므로 다시 되돌아간다. (Back)

순서6 : 다시 이전 지점에서 다른 경로로 진행한다. (Tracking) 1->2->3 이므로 찾는 경우이다. 계속 가본다.

순서7 : 1->2->3->4를 찾았다. 더이상 되돌아가서 진행할 곳 없으므로 종료한다.

 

이처럼 답이 될 가능성이 없는 경로인 경우, 다시 이전 단계로 되돌아가서(Back) 다른 경로를 따라가는 것(Tracking)이 바로 백트레킹(Back Tracking)이다. 위 예시에서는 횟수차이가 얼마 안났지만, 예를들어 노드가 1억개 있는 그래프라면 얼마나 차이가 날지 상상할 수 있을 것이다.

 

 

  사실 Brute Force로 모든 경우를 보는 경우를 생각해보고, 거기서 쳐낼 수 있는 가능성이 있다면 우린 직관적으로 그렇게 하는게 더 좋다는걸 알고있다. 그래서 굳이 나눠서 생각해서 이건 브루트 포스고, 저건 백트래킹이야! 이럴 필요는 없다고 본다. 그냥 모든 경우를 살펴보는 로직을 생각해보고, 중간에 쳐낼 수 있는 경우가 있다면 쳐내자! 최악의 경우엔 어차피 모든 경우를 보게 되겠지만, 일반적으로는 더 효율성 좋은 코드가 된다.

 

 

  백트레킹은 다양한 방식으로 사용할 수 있다. 한 가지 예시를 더 보자.

  시작지점에서 최대 4번까지 이동하면서 당근을 수집하려고 한다. (아무튼 당근임. 그림 못그림.)

처음에 1번루트로 가보니 3개를 발견했다. 그럼 2루트로 진행해서 A지점까지 왔을 때, 더이상 해당 경로를 살펴볼 필요가 있을까? A 지점에 왔을 때 이미 2칸을 왔고, 나머지 2칸에 모두 당근이 있다 해도 최대 2개다. 그러므로 더이상 진행할 필요가 없으니 되돌아와서 루트3으로 간다. 마찬가지로 B까지 왔을 때 더이상 살펴보지 않아도 된다.

 

 

  다음은 백트래킹으로 유명한 N-Queen이라는 문제다. N이라는 숫자에 대해 N x N 크기의 체스판에 N개의 Queen을 서로 공격할 수 없도록 놓는 문제이다.

  위는 N = 4 일 때 놓을 수 있는 경우 중 하나이다. 이 경우 모든 경우를 본다면, 각 칸마다 퀸을 놓거나, 안놓거나 둘 중 하나 이므로 O(2^(4x4))가 된다. 겨우 4x4 짜리 체스판인데도 모든 경우는 65,536가지나 된다. 하지만 백트레킹으로 생각해본다면 다음과 같이 연산을 줄일 경우를 생각해볼 수 있다.

 

1. N x N 크기에 N개를 놓아야하는데, 퀸은 상하좌우로 전체를 공격할 수 있으므로 일단 동일 row, 동일 column에는 퀸을 놓을 수 없다! 즉 각 row와 각 column에는 무조건 하나씩의 퀸만 존재한다.

-> '2'까지 하지 않고, 이것만 해도 연산이 엄청나게 줄어든다.

 

2. 대각선으로도 놓을 수 없으므로 대각선에 대한 체크도 해볼 수 있다. 배열 형태로 체스판을 만들고 어떠한 위치에 놓았다면 실제로 배열에 체크해서 확인해도 되고, 그냥 계산식을 짜서 확인해도 된다. (1번 퀸과 2번 퀸에 대해 두 퀸의 위치의 좌우 차이와 상하 차이의 절대값이 동일하다면 대각선이라고 볼 수 있다.)

 

한번 직접 풀어보고 싶다면 https://www.acmicpc.net/problem/9663 이걸 풀어보면 된다.

 

 

끝.