[알고리즘분석] 4. 되추적

되추적은 어떤 문제에서 계속 검색해나가다가 검색이 중단되었을 때 다시 돌아오는 알고리즘입니다.

이 알고리즘은 게임, 바둑 등에서 다음 수를 찾을 때 이렇게 하면 안되겠다 싶을때 다시 돌아오는 그런 과정을 말하는 것입니다.

미로를 탈출할 때 한 방향으로 쭉 가다가 막혀있으면 더 이상 그 방향으로는 진행하지 않겠죠? 이것과 정확히 일치하는 방식입니다.

0. 되추적의 기초

먼저 트리를 방문하는 방식에는 여러 가지가 있는데, 대표적으로 preorder, inorder, postorder, level order가 있습니다.

preorder, inorder, postorder은 자료구조 시간에 배웠던 내용입니다. 이에 대해서 이전 블로그에 포스팅이 되어있는데, 이쪽으로 옮기지는 않은 상태이기 때문에 간단하게 설명하고 넘어가도록 하겠습니다. (이전 포스팅들은 천천히 옮길 생각입니다!)

preorder는 자신 방문, 좌측 방문, 우측 방문 순으로 방문합니다. DFS를 생각하시면 됩니다!

inorder는 좌측 방문, 자신 방문, 우측 방문 순으로 방문합니다. 보통 작은 수부터 큰 수로 오름차순 진행할 때 쓰죠.

postorder는 좌측 방문, 우측 방문, 자신 방문 순으로 방문합니다. 양쪽 서브트리를 삭제하고 루트를 지워야 할 때 사용됩니다.

level order는 각 레벨 순서대로 방문합니다. BFS를 생각하시면 되겠네요!

preorder의 예시인 DFS(깊이우선탐색)을 복습해보면, root를 먼저 방문한 뒤 그 마디의 모든 후손마디를 차례대로 방문합니다. (마디는 노드와 같습니다)

아래는 DFS의 수도코드입니다.

이 수도코드를 이용하여 DFS 알고리즘을 파이썬을 이용해 구현하였습니다. (위는 재귀버전, 아래는 stack 버전입니다)

테스트코드를 이용하여 잘 돌아감을 확인하였고, 테스트코드를 도식화한 그림과 코드 실행 결과는 아래 사진으로 첨부합니다!

># DFS 재귀
import utility

e = {0:[1,2,3],1:[2,5], 2:[3,4,5,6],3:[4,6],4:[6,7]}
n=8
a = [ [0 for j in range(0,n)] for i in range(0,n)]
for i in range(0,n-1):
    for j in range(i+1,n):
        if i in e:
            if j in e[i]:
                a[i][j]=1
                a[j][i]=1
utility.printMatrix(a)

visited = [] # append로 처리하기 위해 비움

# 맨 처음 작동하면 visited에 0 추가, 그 이후 1에서 재귀문, 순서대로 1 2 3 4 6 7 5 까지 모두 append
# 6까지 가면 더 이상 갈 곳이 없어서 그대로 4로 리턴, 그 다음 u는 7이 들어가게 됨
# 7에서는 이미 방문한 4밖에 갈 수 없으므로 그대로 리턴, 다시 6으로 되추적되고, 4로 되추적되고, 3으로 되추적되고
# 3에서도 5를 갈 수 없으므로 2까지 되추적되어서야 비로소 5가 들어가고 모두 방문했기 때문에 그대로 return되어 마무리된다.
def DFS(a,v):
    global visited
    visited.append(v) # 맨 처음 방문하는 노드 추가
    for u in range(n): # u에 0부터 n-1까지 대입
        if a[v][u] == 1 and u not in visited: # 아직 방문하지 않은 노드중에 연결된 것(a[v][u] == 1)이 있다면
            visited = DFS(a,u) # visited는 DFS(a,u)의 리턴값
    return visited # 다 끝나고 visited 리턴
    
DFS(a,0)

num = 1
for i in visited:
    print(num, i)
    num += 1

# DFS Stack
import utility

e = {0:[1,2,3],1:[2,5], 2:[3,4,5,6],3:[4,6],4:[6,7]}
n=8
a = [ [0 for j in range(0,n)] for i in range(0,n)]
for i in range(0,n-1):
    for j in range(i+1,n):
        if i in e:
            if j in e[i]:
                a[i][j]=1
                a[j][i]=1
utility.printMatrix(a)

visited = [] # 배열 안에 0을 넣는 것

def DFS(a,v):
    global visited
    s = [v] # stack 하나 추가
    while s:
        temp = s.pop()
        if temp not in visited:
            visited.append(temp)
            for u in range(n-1,0,-1): # stack은 거꾸로 빼내기 때문에, stack에 넣을 때 큰 수부터 넣어야 우리가 생각하는 DFS 순서가 된다.
                if a[temp][u] == 1 and u not in visited:
                    s.append(u)
    return visited
    
DFS(a,0)

num = 1
for i in visited:
    print(num, i)
    num += 1

추가로 level order, BFS도 파이썬으로 구현하였으니 참고하시기 바랍니다.

BFS는 queue를 이용하여 구현할 수 있습니다.

# BFS Queue
import utility
import queue

e = {0:[1,2,3],1:[2,5], 2:[3,4,5,6],3:[4,6],4:[6,7]}
n=8
a = [ [0 for j in range(0,n)] for i in range(0,n)]
for i in range(0,n-1):
    for j in range(i+1,n):
        if i in e:
            if j in e[i]:
                a[i][j]=1
                a[j][i]=1
utility.printMatrix(a)

visited = [] # 배열 안에 0을 넣는 것

def BFS(a,v):
    global visited
    q = queue.Queue()
    q.put(v)
    visited.append(v)
    while not q.empty():
        temp = q.get()
        for u in range(n):
            if a[temp][u] == 1 and u not in visited:
                visited.append(u)
                q.put(u)
    return visited
        
    
BFS(a,0)

num = 1
for i in visited:
    print(num, i)
    num += 1

1. 4-Queens 문제

체스판에서 4개의 Queen을 서로를 위협하지 않도록 위치시키는 문제입니다.

서로 상대방을 위협하지 않으려면 같은 행이나 같은 열, 같은 대각선에 위치하면 안됩니다.

여기서 상태공간트리가 등장하는데, 말이 놓일 수 있는 공간들에 대해서 말이 놓이는 경우의 수를 트리 형태로 보여주는 것이 상태공간트리입니다.

4-Queens 문제를 Brute Force(무작정 알고리즘) 방식으로 해결하기 위해서는 각 Queen을 서로 다른 행에 할당한 후에 어떤 열에 위치하면 해답을 얻을 수 있는 지를 차례대로 점검합니다. 각 Queen은 4개의 열 중에서 한 열에만 위치할 수 있기 때문에 해답을 얻기 위해서 확인해야하는 모든 경우의 수는 4*4*4*4 = 256가지가 됩니다.

256가지는 컴퓨터에게 많지 않아보이지만, 체스판이 커질수록 검색횟수가 기하급수적으로 늘어나게 됩니다.

또한 만약 첫 열에 연속으로 퀸이 들어가는 경우 ((1,1), (2,1)) 그 이후부터는 어짜피 앞에서 한번 겹쳤기 때문에 더 이상 확인할 필요가 없습니다. 이후로 계속 검색하는 것은 비효율적인 검색이 되는 것이죠.

이 문제를 보다 효과적으로 해결하기 위해서는 되추적 기술이 필요합니다.

만약 (1,1)에 퀸을 뒀는데, (2,1)에 퀸이 놓여졌다면 더이상 그 경우를 확인하지 않고 다음 (2,2)에 퀸이 놓여진 케이스를 확인하면 되는 것이죠.

여기서 전혀 해답의 가능성이 없는 마디는 유망하지 않다(non-promising)고 할 수 있습니다.

만약 그렇지 않으면 유망하다(promising)고 할 수 있습니다.

이 논리를 생각해서 알고리즘의 동작을 예상해보면 아래와 같습니다.

- 상태공간트리의 깊이우선탐색(DFS)를 실시합니다.

- 각 마디가 유망한지 여부를 점검합니다.

- 만약 그 마디가 유망하지 않다면(더 이상 검색의 의미가 없다면) 그 마디의 부모 마디로 돌아가서 검색을 계속합니다.

이렇게 짠 알고리즘의 수도코드는 아래와 같습니다.

이 방식으로 계산했을 때 총 27마디를 검색하게 됩니다. 만약 유망한지 여부를 체크하지 않은 상태로 DFS를 돌린다면 155마디를 검색하게 됩니다. 차이가 꽤 크죠?

위 알고리즘을 조금 더 개선하면, 아예 방문하기 전에 유망성 여부를 확인하게 만들 수도 있습니다. 이런 식으로 만든다면 방문하는 마디의 수는 더 적어지겠죠.

하지만 쉬운 이해를 위해 본 카테고리의 포스팅에서는 일반 알고리즘으로 표시하도록 하겠습니다. 일반 알고리즘을 개량된 알고리즘으로 변환하는 것은 크게 어렵지 않거든요!

2. n-Queens 문제

4-Queens 문제의 업그레이드 버전입니다.

n개의 Queen을 서로 상대방을 위협하지 않도록 n*n 체스판에 위치시키는 문제입니다.

단순히 4를 n이라는 일반적인 값으로 확장하기만 하면 됩니다.

아래 수도코드를 간략하게 설명하면,

queens는 만약 promising(유망)하다면 if문 안으로 들어갑니다.

만약 i가 n이면 (마지막 행까지 내려왔다면) 경로를 출력합니다.

i가 n이 아니라면 col[i+1]에다가 j를 넣습니다.

그리고 queens에 i+1을 넣어 재귀를 돌려줍니다.

promising은 지금까지 놓은 queen들이랑 현재 위치랑 비교해서 같은 column에 있는지와 같은 대각에 있는지를 확인합니다. 만약 같은 column과 대각에 걸리면 switch를 false로 바꿔줍니다.

같은 대각에 있는지 여부를 확인할 때에는 abs(절대값)을 사용합니다.

col[i]-col[k]의 절대값이 i-k와 같다면 같은 대각에 있는 것입니다.

col[i]-col[k]이 양수면 오른쪽 아래, 음수면 왼쪽 아래로 내려가는 형태가 되겠죠?

이제 상태공간트리 전체에 있는 마디의 수를 구해봅시다.

깊이가 i일 때 마디의 개수는 n^i개이고, 이 트리의 깊이는 n이므로

확인하는 마디의 총 개수의 상한은 1+n+n^2+n^3+....+n^n = n^(n+1)-1/n-1입니다. (맨 윗 노드를 포함합니다)

이걸 등비수열의 합으로 생각하면 n^(n+1) -1 / n-1이 되겠죠!

한 마디에 n개씩 연결되어있고, 이게 n level만큼 반복되기 때문입니다.

만약 n=8이라면 8^9 -1 / 8-1 = 19173961이 됩니다.

하지만 이렇게 마디수의 최대값을 구하는 것은 이 알고리즘의 동작에 있어서 크게 의미가 없습니다.

되추적 알고리즘을 통해 얼마나 검색하는 마디 수를 줄였는지에 대한 정보가 더 중요하기 때문이죠.

이번엔 같은 열에 위치할 수 없다는 제약조건을 걸고 마디의 수를 세어보면,

n=8일 때 첫 줄에는 8칸 중 아무 칸이나 가능하고, 그 다음에는 7칸, 또 그 다음엔 6칸에 놓을 수 있습니다.

이걸 반복하면 유망한 마디의 수는 1+n+n(n-1)+n(n-1)+n(n-1)(n-2)+....+n!가 됩니다.

하지만 위 두 가지 방법은 알고리즘의 복잡도를 정확히 설명해 주지는 못합니다.

대각선을 점검하는 경우를 전혀 고려하지 않았기 때문입니다.

유망한 마디의 개수를 정확하게 구하기 위한 유일한 방법은 알고리즘을 돌려서 구축된 상태공간트리의 마디 수를 세어보는 것입니다. 하지만 알고리즘을 실제로 수행해야 하기에 진정한 분석 방법이라고는 볼 수 없습니다.

아래 표를 보시면 무작정 알고리즘의 방법과 대각선을 고려하지 않은 경우의 수, 일반적인 백트래킹시 마디의 수와 백트래킹에 의해 Promising이라고 밝혀진 마디의 수를 알 수 있습니다.

백트래킹에 의해 추려낸 유망한 마디의 수가 월등히 적은 것을 알 수 있습니다.

아래는 파이썬으로 구현한 n-Queens 알고리즘입니다.

n=7일 때의 경우의 수를 모두 출력하도록 만들었습니다.

# n-Queens 문제 해결 알고리즘
def promising(i,col):
    k = 0
    switch = True
    while(k<i and switch==True): # k가 i보다 작고, 아직 유망하다면 (switch가 True라면)
        if(col[i]==col[k] or abs(col[i]-col[k])==i-k): # col[i]를 col[0]부터 col[i-1]까지 비교 - 같은 행 or 같은 대각선 확인
            switch = False # 그럼 switch를 False로
        k += 1 # k 1 증가
    return switch


def queens(n,i,col): 
    if promising(i,col): # 만약 i번째 depth column에서 유망하면
        if i == n-1: # 끝까지(여기서는 index 6까지) 말을 놨다면
            print(col) # column을 출력한다
        else: # 아직 말을 놓지 않은 column이 존재하면
            for k in range(n):
                col[i+1] = k # 다음 column의 모든 칸에 말을 놓은 후에
                queens(n, i+1, col) # 다시 queens를 돌린다

n=7
col=n*[0] # col[i]는 i번째 queen이 위치한 column값
queens(n,-1,col)

특정 번째의 해를 출력하고, 해의 총 개수를 출력하는 코드도 짜보았습니다.

# n-Queens 문제 해결 알고리즘 (특정 col만 출력, 해의 총 개수 출력)
def promising(i,col):
    k = 0
    switch = True
    while(k<i and switch==True): # k가 i보다 작고, 아직 유망하다면 (switch가 True라면)
        if(col[i]==col[k] or abs(col[i]-col[k])==i-k): # col[i]를 col[0]부터 col[i-1]까지 비교 - 같은 행 or 같은 대각선 확인
            switch = False # 그럼 switch를 False로
        k += 1 # k 1 증가
    return switch


def queens(n,i,col): 
    global count
    if promising(i,col): # 만약 i번째 depth column에서 유망하면
        if i == n-1: # 끝까지(여기서는 index 6까지) 말을 놨다면
            count += 1 # count 1 증가
            if count == 3: # 세 번째 해에 도착했다면
                print(col) # column을 출력한다
        else: # 아직 말을 놓지 않은 column이 존재하면
            for k in range(n):
                col[i+1] = k # 다음 column의 모든 칸에 말을 놓은 후에
                queens(n, i+1, col) # 다시 queens를 돌린다

count = 0 # 해 개수 확인용
n=7
col=n*[0] # col[i]는 i번째 queen이 위치한 column값
queens(n,-1,col)
print("해의 총 개수 : %d" %count)

n-Queens 문제와 같은 방식으로 바둑 역시 가능한 모든 수를 구해서 최선의 수를 구해낼 수 있습니다. 이것이 발전된 형태가 알파고가 되는 것이죠. 신기하지 않나요?!

2. 부분집합의 합

이번엔 n개의 아이템을 이용하여 item들의 무게의 합이 W가 되는 부분집합을 구하는 알고리즘입니다.

만약 S={2,4,5} 라고 하고, 합이 6가 되는 부분집합을 구한다고 하면 아래와 같이 경우의 수를 구해서 해답을 구할 수 있습니다.

무게를 오름차순으로 정렬하고 하나하나 넣어보면 됩니다. w_(i+1)을 넣을 수 없게 되는 순간 w_(i+1) 이후는 고려할 필요가 없어집니다.

weight를 i마디까지 포함된 무게의 합이라고 생각하고, total이 남아있는 아이템 무게의 합이라고 정의한다면

weight + w_(i+1) > W (if weight != W) -> 다음꺼 더하면 W를 초과하니까 꽝!

weight + total < W -> 남은거 다 더해도 목표무게 불가능

두 경우에는 더이상 유망하지 않다고 고려할 수 있습니다.

이 알고리즘에 대한 수도코드는 아래와 같습니다.

만약 유망한 경우에는 W와 현재까지 무게가 같으면 아이템들을 출력하고, 아니라면 다음 요소를 넣는 경우와 넣지 않는 경우를 생각하여 재귀함수를 돌려줍니다.

promising 함수의 경우 위에서 확인했던 promising이 되지 않는 두 가지 경우를 걸러낸다면 true, 두 조건에 걸려버리면 false를 반환하면 됩니다.

수도코드를 바탕으로 파이썬 코드를 작성하였습니다.

테스트코드는 w가 순서대로 1,2,3,4,5,6이고 목표하는 무게는 9일 때의 결과를 출력하도록 만들었습니다.

각 인덱스에 위치한 값이 1이면 포함하고 0이면 포함하지 않는 경우입니다!

def promising(i,weight,total):
    # total과 weight의 합이 W보다 크고 weight가 W랑 같거나 weight+w[i+1]이 W보다 작거나 같으면 true
    return (weight + total >= W) and (weight == W or weight + w[i+1] <= W); # 가능성 확인 / 출력용 + 가능성 확인

def s_s(i,weight, total, include):
    if promising(i, weight, total):
        if weight == W:
            print(include)
        else:
            include[i+1] = 1
            s_s(i+1, weight+w[i+1], total-w[i+1], include)
            include[i+1] = 0
            s_s(i+1, weight, total-w[i+1], include)

    
n=6
w=[1,2,3,4,5,6]
w.sort() # w 정렬
W=9
print("items =" , w, "W =", W)
include = n*[0]
total=0
for k in w:
    total += k
s_s(-1,0,total,include)

3. 그래프 색칠하기

어렸을 때 수학문제 중에서 인접한 나라에 겹치지 않도록 지도에 색칠하는 문제가 있었던게 어렴풋이 기억에 남습니다.

그 때는 문제를 못 풀었던 것 같은데, 이 문제 역시 되추적의 대표적인 문제 중 하나입니다.

결과를 먼저 말하면 단 4개의 색깔만 있으면 인접하는 지역을 구분하도록 색깔을 할당할 수 있습니다.

먼저 문제를 단순화 하기 위해서 map을 graph로 바꿔보도록 하겠습니다.

각 지역은 node가 되고, 만약 인접해 있다면 두 node는 연결됩니다.

그리고 모든 map은 graph 중에서도 planar graph(평면그래프)로 연결이 가능합니다.

planar graph(평면그래프)는 평면 상에서 이음선(edge)들이 서로 엇갈리지 않게 그릴 수 있는 그래프를 말합니다.

위는 평면 그래프, 아래는 비평면 그래프의 예시를 가져왔습니다.

이제 map을 graph로 바꿨으니 실제로 몇 가지 색으로 색칠할 수 있는 지에 대해서 알아봅시다.

아래 사진의 그래프를 두 가지 색으로 구분하는 방법은 없습니다.

v1에 빨간색을 칠하고, v2와 v4에 파란색을 칠한다고 생각하면 v3에서는 칠할 수 있는 색이 없죠.

다른 경우도 마찬가지입니다. (실제로 2개의 색으로만 구분할 수 있는 경우는 cycle이 아예 없는 경우 뿐입니다.)

따라서 3가지 색깔로 색칠한다고 생각하면 되추적 방식으로 아래와 같이 해답을 구할 수 있습니다.

다음은 수도코드입니다.

promising 함수는 인접한 위치에 있는 마디(node)들은 같은 색이 되면 안된다는 것을 체크합니다.

그게 while문의 if절 안에 들어간 조건문이고, 만약 인접했는데 같은 색이라면 switch를 false로 바꿉니다.

m_coloring 함수는 유망하면 다음 마디에 모든 색을 넣어서 m_coloring(i+1)로 재귀를 돌립니다.

이제 다음 마디에서 유망하지 않으면 걸러지고, 유망하면 또 색들이 칠해지고..의 반복이 되는 것이죠.

아래는 위 문제를 파이썬으로 구현한 코드입니다. vcolor이라는 array를 미리 만들어놓고 그 안에서 진행한다는 것만 추가되었고 나머지는 위 수도코드를 이해했다면 쉽게 이해하실 수 있습니다.

def color(i,vcolor):
    if promising(i,vcolor): # 맨 처음에는 promising이 무조건 True, 마지막은 i==n-1이 되는 순간 print되서 종료
        if (i==n-1):
            print(vcolor)
        else:
            for j in range(1,m+1):
                vcolor[i+1] = j
                color(i+1, vcolor)

def promising(i,vcolor):
    switch = True
    j = 0
    while j<i and switch:
        if W[i][j] and vcolor[i]==vcolor[j]:
            switch = False
        j += 1
        
    return switch

n=4
W=[[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]]
vcolor=n*[0]
m=3
color(-1,vcolor)