Backtracking(되추적) 알고리즘이란 큰 공간에서 하나의 해를 찾아가는 도중 올바른 해가 아니여서 막히면 다시 돌아와서 해를 찾아가는 기법이다.
Backtracking은 DFS 와의 차이를 비교하며 살펴보면 이해하기 더 쉽다.
DFS(Depth First Search, 깊이우선탐색)
DFS, 깊이우선탐색은 그래프에서 root를 먼저 방문한 뒤 그 root의 후손들을 방문하면서 가장 깊숙히 위치하는 노드에 닿을 때까지 순회하는 방법이다.
즉, 트리 순회 중 preorder(루트 -> 왼 -> 오) 방식을 사용하고 있는 것이다.
DFS의 c++ 수도 코드와 python 코드를 살펴보자
<c++>
void depth_first_tree_search(node v) {
node u; // 자식 노드
visit v; //현재 루트노드 먼저 방문
for (each child u of v) //재귀함수 호출로 루트의 자식노드들을 순회
depth_first_tree_search(u)
}
<python>
다음 그래프를 예시로 들어 코드를 작성하였다.
#graph: 인접 리스트
# v : 노드번호
# visited : 방문한 노드 처리 스택
def dfs(graph, v, visited):
#현재 노드(루트) 방문 처리
visited[v] = True
# 방문한 노드 출력
print(v, end = ' ')
# 현재 노드(루트)의 자식노드 중 방문하지 않은 노드들 재귀적으로 방문
for i in range graph[v]:
if not visited[i]:
dfs(graph, i , visitied)
graph = [
[], # 0번 노드와 연결된 노드 : 없음
[2,3,8], # 1번 노드와 연결된 노드 : 2,3,8
[1,7], # 2번 노드와 연결된 노드 : 1, 7
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문한 정보를 표현하는 1차원 리스트
# False 로 초기화
visited = [False]*9
#Index 0은 사용하지 않기 때문에 1번노드부터 호출
dfs(graph, 1,visited)
Backtracking(되추적 기술)
되추적이란?
- 어떤 노드의 유망성(promising)을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 부모 노드로 돌아가서 (Backtrack) 다음 후손노드에 대한 검색을 계속하는 절차이다.
- 이때 부모 노드로 돌아가면서 가지를 침으로써(pruning) 트리의 크기를 축소시킬 수 있다.
- 이 과정에서 방문한 노드로만 구성된 부분트리를 가지친 상태공간 트리(pruned state space tree)라고 한다.
노드의 유망성(promising)?
- 전혀 해답이 나올 가능성이 없다면 유망하지 않다. (non-promising)
- 그렇지 않다면 유망하다!(promising)
backtracking 알고리즘 절차
1. 상태공간트리(가능한 해로 이루어진 트리) 에서 DFS 실시
2. 각 노드가 유망한지 점검
3. 유망하지 않다면 그 노드의 부모 노드로 돌아가서 검색 계속
되추적 알고리즘을 수도코드로 나타내면 다음과 같다.
void checknode(node v) {
node u; // 자식 노드
if (promising(v)) // 해당 노드가 유망하다면
if (there is a solution at v)
write the solution;
else
for (each child u of v) // v 노드의 다른 child 노드를 방문
checknode(u); // child 노드(u)에 대해 재귀적으로 함수 호출
이제 N-queens 문제를 통해 Backtrackingr과 DFS 와의 차이점을 알아보자.
👸 N-queens 👸
- N개의 Queen을 서로 상대방을 위협하지 않도록 n x n 체스판에 위치시키는 문제
- 서로 상대방을 위협하지 않기 위해 같은 행, 열, 대각선 상에 위치하지 않아야한다.
N을 4라고 가정해보자.
그렇다면 4개의 Queen을 4x4 체스판에 같은 행,열,대각선에 위치하지 않도록 배치해야한다.
DFS 알고리즘 적용
DFS, 무작정 알고리즘으로 이 문제를 해결하기 위해서는 4개의 queen들이 배치될 수 있는 경우의 수를 모두 고려해야한다.
각 queen을 다른 행에 배치했을 때, queen은 4개의 열 중 한 열에 위치할 수 있기 때문에 해답을 얻기 위해 점검해야할 경우의 수는 4x4x4x4 = 256개가 된다.
상태 공간을 계층적으로 표시하게 된다면 다음과 같다.
Backtracking 알고리즘 적용
노드가 promising 하다면 그 노드의 자식 노드를 검색하기 때문에 DFS의 상태공간 트리보다 훨씬 작아진 트리를 확인할 수 있다.
DFS vs Backtracking
DFS 의 검색 노드 = 155개
Backtracking 검색 노드 = 27개
backtracking 은 노드를 방문하기 전에 유망성의 여부를 점검하기 때문에 그만큼 방문하는 노드의 수가 적어져서 효율적이다.
DFS보다 더 효율적인 backtracking으로 N-queens 문제를 해결해본다.
Backtracking 알고리즘을 사용하기 위해 고려할 부분은 다음과 같다.
1. 상태 공간 트리의 구조를 결정
N-queens의 문제에서는 n개의 행을 level로 나눈다.
즉, 총 n개의 level을 가지고 각 level에서 n개의 열을 노드로 둔 트리 구조이다.
이는 전체적인 트리 구조이며, 유망한지의 여부에 따라 각 level에서의 노드는 n개가 되지 않을 수도 있다.
2. 유망함의 기준 (어떤 부분에 대해서 유망한지 아닌지를 결정할 것인가?)
다음은 promising에 대한 기준을 정해야한다. 유망성의 기준은 문제에 그대로 나와있다.
우리는 퀸을 서로 충돌하지 않게 둬야한다!
대각선에서는 충돌하는 퀸이 없는지, 또 같은 열에 있는 퀸이 없을 때 유망하다고 할 수 있다. (퀸을 1행부터 n행까지 순서대로 두기때문에 행이 겹칠일은 없다.)
즉, 대각선과 열, 이 두가지를 검사해야한다.
이러한 검사 과정을 담은 것이 promising function이다. 이를 코드로 표현하면 다음과 같다.
각 행에 하나의 queen만 위치 하기 때문에 col[i] 는 i번째 queen이 위치한 칼럼값이 된다.
<promising function>
1) 열에 대해 검사
두 queen이 같은 열에 있다면 nonpromising하다.
if(col[i] == col[k])
nonpromising;
2) 대각선에 대해 검사
두 queen이 서로 같은 대각선 상에 있는지 확인하기 위해서는 두 행의 차와 열의 차의 절댓값을 비교하면 된다.
if(abs(col[i]-col[k]) == abs(i-k))
nonpromising;
이제 n-queens 문제에 되추적 알고리즘을 적용하기 위한 준비가 모두 끝났다!
n-queens 문제를 해결하기 위한 코드를 작성해보자
앞서 구상한 promising 함수는 해당 노드가 유망하다고 판정나면 해당 노드의 자식 노드를 재귀적으로 탐색하게 된다.
다음은 c++로 구현한 수도코드이다.
void queens(index i) {
index j; // j번째 행에 있는 queen
if (promising(i) {
if (i == n) // i번째 노드가 마지막 노드(마지막 행)까지 도달해야 모든 queen들을 다 배치한 것이기 때문에 답을 찾을 수 있음
cout << col[1] through col[n]
else
for (j=1 ; j<=n; j++){ // i+1번째 queen을 위치 시키는 코드
col[i+1] = j;// i+1번째 queen을 j번째 열에 놓기
queens(i+1); // i+1번째 queen에 대한 재귀 호출로 해당 위치가 적합한지 유망성을 검사
}
}
bool promising(index i) {
index k;
bool switch;
k = 1; // k는 1부터 i-1까지 순회하면서 현재 i와 조건에 부합한지 검사
switch = TRUE;
while(k < i && switch) {
if (col[i] == col[k] || abs(col[i] - col[k]) == i-k)
switch = false;
k++;
}
return switch;
}
python으로 작성한 코드이다.
#n : queen개수, nxn 체스판
n = int(input())
ans = 0
row = [0] * n #체스판 초기화
total_nodes = 0 # 총 노드의 수를 세기 위한 변수
def n_queens(x) :
global ans, total_nodes, answer_10 # 해의 총 개수를 세기 위해 전역변수
if x == n : # 마지막 행(= 마지막 queen)까지 위치시켰다면 해답을 찾은 것
ans += 1
return
else : # 아직 queen을 다 위치시키지 못한 것이기 x번째 queen을 n개의 열에 한번씩 위치시키면서 유망성 검사
for i in range (n) :
total_nodes += 1 # 하나의 열에 둘 때마다 node는 1씩 늘어남
row[x] = i # x번째 queen을 i번째 열에 위치시키는 것 = (x, i)에 위치 시키는 것
if promising(x) : # 유망하다면 다음 queen에 대해서 유망성 검사
n_queens(x+1)
def promising(x) :
for i in range(x) : # 0부터 x-1행(queen)까지 현재 queen(x)과 2가지 조건을 만족하는지 검사
if (row[x] == row[i]) or (abs(row[x] - row[i]) == abs(x-i)): # 같은열, 같은 대각선에 위치한다면 false
return False
return True
n_queens(0) #0번째 queen부터 시작
print('전체 해의 개수 :', ans)
print('상태 공간 트리의 모든 노드의 수 :', total_nodes)
알고리즘 복잡도 분석 🤖
N-Queens 문제의 분석 1️⃣ : 전체 노드의 수를 구해서 upper bound를 구해보자
상태공간트리 전체에 있는 노드의 수(가능한 모든 해)를 구함으로써 가지친 상태의 공간트리의 노드의 개수를 상한을 구해본다.
깊이가 i 인 노드의 개수는 n^i개 이고, 이 트리의 깊이는 n이므로, 노드의 총 개수의 상한(upper bound)는 다음과 같다.
하지만 상한값을 구하는 분석은 별 의미가 없다. 왜냐하면 상한값을 구해도 backtracking을 통해 노드의 수를 얼마나 줄였는지 알 수 없기 때문이다.
N-Queens 문제의 분석 2️⃣ : 유망한 노드만 세서 upperbound를 구해보자
promising 한 노드만을 세기 위해서는 queen이 같은 열상에 위치할 수 없다는 조건을 이용하면 된다.
첫번째 queen은 n개의 어떤 열에도 위치시킬 수 있고, 두번째는 남은 n-1열 중에서 위치시킬수 있다.
세번째는 남은 n-2개 중 위치시킬 수 있게 된다.
이런식으로 계속해서 유망한 노드 수를 세게되면 이 공식을 통한 값을 넘지 못하게 된다.
하지만 이 방법도 알고리즘의 복잡도를 설명해주지 못한다. 그 이유는 대각선에 대한 조건을 고려하지 않았으므로 유망하지않은 노드를 포함할 수 있기 때문이다.
N-Queens 문제의 분석 3️⃣ : 실제 알고리즘 결과로 나온 노드의 수를 세어보자
결국, 유망한 노드의 개수를 정확히 구하기 위한 유일한 방법은 실제로 알고리즘을 수행하여 구축된 상태공간트리의 노드의 개수를 직접 세어보는 수밖에 없다.
하지만 분석이란 알고리즘을 실제로 수행하지 않고 이루어져야하기 때문에 진정한 분석 방법이라고 할 수는 없다.
'알고리즘' 카테고리의 다른 글
[삼성 SW 역량테스트 기출] 백준 14502번 연구소 (2) | 2024.01.20 |
---|---|
[삼성 SW 역량테스트 기출] 백준 14499번 주사위 굴리기 (0) | 2024.01.19 |
[삼성 SW 역량 테스트 기출] 백준 14501번 : 퇴사 (0) | 2024.01.16 |
[이코테] 숫자 카드 게임 - Python, 그리디 (0) | 2023.07.20 |
[이코테] 큰 수의 법칙 - Python, 그리디 (0) | 2023.07.19 |