엔퀸즈 문제를 풀다가 백트래킹이라는 게 나왔고. 백트래킹이 뭔지 몰라서 검색했었는데, 그 검색한 시간이 조금 짧은 것 같아서 정리를 하며 마저 공부를 해 볼까 한다. 백트래킹이 뭔지 정말 1도 몰르는 사람에게는 유익하기를 바라며.
엔퀸즈? N Queens
체스를 둬 본 적이 있나요? 일단 저는 없습니다. 포커는 해 봤어도 체스는 한 번도 해 본 적이 없는데, 룰을 읽으니 장기와 비슷하다는 것을 알겠더라구요. 각각의 말들이 갈 수 있는 칸과 위치가 있고, 그것들을 이용해서 상대방의 말을 다 잡으면 되는 게임이라고 해요. 그렇다면 엔 퀸즈는 뭐냐.
퀸이라는 말을 한 판 안에 겹치지 않고 n의 개수만큼 놓을 수 있는 방법을 찾으면 됩니다.판이 4줄이라면 4 개, 판이 5 줄이라면 5 개처럼요.
퀸은 가로, 세로, 대각선으로 옮길 수 있고, 칸은 정해져 있지 않습니다.
만약 제일 첫번째, 위의 자리에 첫 번째 퀸을 놓았다고 가정을 한다면..
이런 식으로 3개밖에 놓을 수 없으니 이건 성공하지 못한 방법이 되겠네요.
퀸이 엔 개 들어갈 수 있는 방법은 항상 있습니다. 다만, 다 되는 게 아닌 것일 뿐입니다. 그렇기 때문에 모든 경우의 수를 조사하여, 가능한 방법만 찾아내는 것이 엔퀸즈 알고리즘입니다.
그게 백트래킹이랑 무슨 상관..?
엔퀸즈는 모든 경우의 수를 내는 게 아니라 조건에 맞는 경우의 수만 조합하는 것이고, 그게 요지인데, 그걸 백트래킹이 해냅니다.
백트래킹이 뭐예요?
알고리즘의 종류 중 하나, 그러니까 문제를 풀기 위한 방식 중 하나인데요, 백트래킹을 한글로 번역하면 '역추적'이 됩니다. 이게.. 뭘까요? 역추적? 그냥 다시 뒤로 돌아가는 건가? 위키디피아를 보니 CSP(Constrain Satisfaction Problems)를 해결하기 위해서 사용한다고 쓰이네요.
조건 만족 문제를 해결하기 위한다? 모든 조합 중에 조건을 만족하는 것만 살펴 본다는 뜻. 그래서 엔퀸즈 문제가 대표적인 백트래킹 문제라고 볼 수 있습니다.
어떻게 모든 조합 중에 조건을 만족하는 것만 살필 수가 있을까요?
정답은 배제입니다.
어떤 유망해 보이는 루트를 검사했을 때, 유망하지 않다고 판단이 되면 다시 그 부모의 루트로 돌아간 후 다른 자식의 유망 루트로 검색을 하는 것을 말하는데요. 엔퀸즈에 대입해서 설명하자면 이렇습니다.
첫 번째 퀸을 놓았을 때 가능성이 열려 있다면 두 번째 퀸을 놓습니다. 두 번째 퀸을 놓았을 때 가능성이 열려 있다면 세 번째 퀸을 놓습니다. 세 번째 퀸을 놓았을 때 네 번째 퀸을 놓을 수 있다면 놓겠지만, 세 번째 퀸을 놓고 네 번째 퀸으로 가려고 했을 때 네 번째 퀸의 자리가 없으므로, 네 번째까지 갈 필요도 없이 이 루트는 성공할 수 없는 루트라고 판단하여 다시 제일 위로 올라갑니다. 그리고 다음 노드를 실행합니다.
또한, 하나의 루트가 어느 지점에서 실패를 하게 되면 그 루트의 자식 루트를 여러 방법으로 돈다고 해도 실패를 한다고 생각하기 때문에, 그 실패한 루트의 다른 자식 노드까지 둘러보지 않고 바로 다음으로 넘어갑니다. 그렇기 때문에 조건이 적을 경우엔 빠르게 탐색하고 빠져나갈 수 있겠죠.
이 방식은 DFS로 주로 탐색을 하는데요, DFS로 하게 되면 메모리 소비량이 적다고 합니다. 그도 그럴 이유인 게, 하나의 루트가 어느 지점에서 실패를 하게 되면 그 루트의 자식 루트를 여러 방법으로 돈다고 해도 실패를 한다고 생각하기 때문 이런 이유에서, 실패한 루트는 더 돌지 않기 때문에 전체를 다 돌아보는 것보다 부분적으로 빠르게 돌리는 게 더 낫겠죠?
그림으로 보면 더 이해하기 쉽습니다. 실패한 루트의 자식 루트가 8 개여도, 1 개를 검사하여 실패한 이상 더 이상 그 자식 루트는 돌지 않고 다시 뒤로 돌아갑니다.
간단하게 수도 코드로 말해 보자면..
- 카운트 변수를 만든다. (초기 설정값은 0)
- n*n의 보드를 만든다.
- 재귀를 돌릴 함수를 만든다. 이때, 매개변수는 0이다. (제일 첫 가로줄의 인덱스를 뜻함)
- 만약, n과 매개변수가 같으면 카운트를 세고, 리턴한다.
4-1. 그 이유는, 가로의 끝까지 재귀가 다 돌아갔을 경우, 성공했다고 보기 때문이다. - board의 row 수만큼 반복문을 둔다.
- board의 제일 첫 번째 칸에 퀸을 둔다.
- 만약 퀸을 넣었을 때 충돌하지 않는다면, 해당 함수를 재귀로 돌려 다음 줄로 넘어간다. (조건 검사 실행)
- 그렇지 않다면 뒀던 퀸을 회수한다.
- 한 칸의 조건 검사가 끝나면 다음 칸으로 넘어간다.
- 카운트를 리턴한다.
이런 방식이 된다.
수 읽는 것에 실패했을 경우, 아래에 있는 모든 자식의 노드를 돌아보지 않아도 실패로 간주하고 다시 올라가는 모습을 볼 수 있다.
