목적
내가 백트래킹, DFS, N-Queen을 까먹었을 때를 대비해서 나를 다시 가르치는 느낌으로 글을 써보겠다.
1. 백트래킹(backtracking)
1) 백트래킹이란?
백트래킹은 모든 경우의 수를 고려하여 해를 찾는 방식을 말한다. 이름에서 유추할 수 있듯이, 퇴각 검색(추적)이라는 의미를 갖는다. 해를 찾기 위해 후보군을 나열하고, 제약조건을 점진적으로 체크한다. 만약 조건에 맞지않다면, 뒤로 돌아와서(backtrack), 바로 다음 후보군으로 넘어간다. 백트래킹에서 검색할 후보들을 상태 공간 트리(State Space Tree)로 표현한다.
2) 상태 공간 트리(State Space Tree)
루트 노드로 부터 검색을 진행한다. 검색을 진행할 때마다 조건에 맞는 해인지 체크를 해줘야한다.
깊이탐색 진행
백트래킹은 트리구조 기반으로 DFS(깊이 우선 탐색)를 진행한다.
그래프 탐색이란?
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것을 말한다.
깊이 우선 탐색(DFS, Depth-First Search)
깊이 우선 탐색이란?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
깊이 우선 탐색(DFS)의 특징
자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
전위 순회(Pre-OrderTrabersals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
-
a 노드(시작 노드)를 방문한다.
방문한 노드는 방문했다고 표시한다. -
a와 인접한 노드들을 차례로 순회한다.
a와 인접한 노드가 없다면 종료한다. -
a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
-
b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
아직 방문이 안 된 정점이 없으면 종료한다.
있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.
만약 조건에 부합하지 않다면, 더 이상 탐색을 진행하지 않는다. 이후 그림처럼 이전 상태로 돌아간뒤, 다음에 해당하는 노드를 검색한다.
b의 자식 노드인 f도 조건에 맞지 않다면, b이하는 모두 해가 될 수 없다.그래서 이때는 a상태로 돌아가서 c부터 다시 탐색을 진행한다.
3) 백트래킹 관련 용어
Promising: 해당 루트가 조건에 맞는지 검사하는 기법이다.
Pruning(가지치기): 조건에 맞지 않으면 포기하고, 다른 루트로 바로 돌아서서 탐색의 시간을 절약
백트래킹은 트리 구조를 기반으로 DFS방식을 진행하면서 각 루트에 대해 조건에 부합했는지 체크(Promising)를한다.
만약 해당 트리에서 조건에 맞지 않는 노드를 발견한다면, 더 이상 탐색을 멈추고, 다른 노드로 가지를 친다(Pruning).
2. N-Queen
NxN의 체스판(보드판)에 N개의 퀸을 두는 방법을 제시하는 것이다. 이때 배치할 퀸은 다른 배치된 퀸과 이동경로가 겹쳐서는 안된다.
NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다.
퀸은 수직, 수평, 대각성으로 이동가능하다.
조건을 주는 방법으로는 이런 방법이있다.
- 4 x 4 체스판을 행과 열로 이루어진 테이블을 만든다.
4 x 4 체스판- 가장 먼저는 행과 열이 0인 [0,0 지점]을 루트 노드로 탐색을 시작한다.(0,0 부분에는 퀸을 배치해준다.)
회색 칸은 조건에 따라 다음 퀸을 배치할 수 없는 위치이다.(퀸의 이동경로이다.)
조건에 따라 다음 퀸은 이미 배치된 퀸과 같은 열에 위치할 수 없다. 다음 퀸은 1번열 중에 배치해야한다. 이제 1,0부터 1,3을 순차적으로 체크한다. 퀸의 이동방향이 수직 또는 대각선이기 때문에 1,0과 1,1에는 다음 퀸을 배치할 수 없다. 그렇다면 남은 1,2와 1,3에 배치할 수도 있다.
- [1,2 지점]에 두번째 퀸을 배치한다.
위 그림은 1,2에 해당하는 위치에 두번째 퀸을 둔 모습이다. 이제 세 번째 퀸을 배치하기 위해서 다음 열인 2번열을 0행부터 3행까지 탐색을 진행한다. 하지만 그림을 보면 이미 앞에서둔 퀸들로 인해서 세 번째 퀸을 배치할 수 없게 되었다.
이럴때 백트래킹을 사용해줘야한다. 1,2위치는 잘못된 위치라는것을 알고있다. 따라서 두 번째 퀸을 1,2에서 제거하고 1,3으로 이동한다. 그다음으로는 똑같이 가지를 치고 탐색을 진행한다.
- [1,2 지점]의 퀸을 제거하고, [1,3 지점]에 두번째 퀸을 배치한다. 동일한 방법으로 더 이상 퀸을 둘 수 없거나, 모두 둘 때까지 진행한다.
[0,0 지점]을 노드로 한 경우는 3번 열에서 퀸을 배치할 수 없게 된다. 즉 0,0 지점에 퀸을 배치하는 것부터 잘못이다. 동일하게 첫 번째 퀸을 옆 칸인 0,1로 이동시킨다. 그 다음으로는 똑같이 가지를 치고 탐색을 진행한다.
- [0,1 지점]을 루트 노드로 탐색을 진행
조건에 맞게 반복적으로 가지치고 탐색을 진행하면 다양한 해가 나올텐데 그중 첫 번째 결과에 해당한다.
마무리
백트래킹, DFS, N-Queen 관련 개념들은 코딩테스트에서 자주나오는 단골문제이다. 하지만 나는 관련 개념들 조차 몰랐고 무작정 공부를 하다보니깐 공부하는데 있어서 어려움을 느꼈다. 어려움을 극복하기 위해서 관련된 개념들을 하나씩 찾아보면서 천천히 공부를해서 어떤식으로 동작하는지 알 수 있게 되었다.
