14. 백트래킹 (Backtracking)

- 그래프 알고리즘에서 배운 DFS를 빼고는 백트래킹을 이야기할 수 없음, DFS는 백트래킹의 골격을 이루는 알고리즘 !

- 깊이 우선 탐색 (DFS)의 방식으로 탐색하는 모든 방법을 이야기한다.

- 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었고, 백트래킹은 주로 재귀적으로 구현한다.

-백트래킹 알고리즘마다 DFS에서 조금씩 변형은 일어나지만 모두 DFS의 범주에 속하며, 백트래킹 알고리즘이 상태 공간 트리를 명시적으로 만드는 것은 아니지만 알고리즘의 진행 과정은 상태 공간 트리의 루트에서 시작해서 DFS 방식으로 탐색해나가는 것이다.

 

** 그 전에 그래서 백트래킹이 뭔데?

백트래킹 알고리즘이란 퇴각 검색이라고도 불리며 이는 한정 조건을 가진 문제를 풀려는 전략

쉽게 설명해서, 어떤 문제를 푸는 것에 있어 모든 경우의 수를 시도하여 문제의 정답을 찾아나가는 것

하지만 백트래킹에서는 한정 조건에서의 모든 경우의 수를 시도하는 것이기 때문에 실제로 상당한 경우의 수들이 배제되므로, 단순 다중 for 루프보단 빠르게 문제가 해결되는 경우가 많다.

 

 

 

1. 미로 찾기 문제

- S는 시작지점이고 T는 목표지점으로 설정하고 본다면, 이 미로 찾기 문제의 탐색 과정은 상태공간트리로 표현이 가능해지게 된다. 이 상태트리에 대한 설명은 다음과 같다.

-S에서 시작해 정점 1로 이동한다. 이후 정점 2 또는 3 중 하나를 선택할 수 있다.

-임의로 정점 2를 선택하였다. 2에 도착하니 막다른 골목임을 알게 된다.

-정점 2로 오기 위해 거쳤던 중간 지점 1로 되돌아간다. 이제 정점 3으로 가보는 수밖에 없다.

-정점 3으로 이동한다. 여기서는 정점 4와 5 중 하나를 선택할 수 있다. 정점 5를 선택한다고 하자.

-정점 5에 이른다. 정점 6과 7 중 하나를 선택할 수 있다. 정점 6을 선택한다고 하자.

-정점 6에 이른다. 도착해보니 정점 6이 막다른 골목임을 알게 된다.

-정점 6을 오기 위해 거쳤던 중간 지점 5로 다시 되돌아간다. 이제 정점 7로 가보는 수밖에 없다.

-정점 7에 이른다. 정점 8과 정점 T 중 하나를 선택할 수 있게 된다. 정점 T를 선택한다고 하자.

-정점 T에 도착하니 목표지점임을 알게 된다. 탐색을 종료한다.

 

-백트래킹은 위와 같이 가 보고, 되돌아오는 과정을 무한히 반복하는 것이다. 운이 좋으면 시행착오를 덜 거치고 목적지에 도착할 것이고, 최악의 경우에는 모든 경우를 다 거친 다음 목적지에 도착할 수 있게 된다.

maze(v):
	v.visited= YES
    if(v==T): return "success"
    for each x is in v.adjlist
    	if(v.visited=NO):
        	v==x.prev
            	maze(x)

-알고리즘이 끝난 후 S에서 T에 이르는 경로를 알려면 T에서 시작해 prev[]를 통해 따라간다. 그렇다면 시작 지점에 이르게 되는 것이다.

-이의 역방향은 해답 경로다.

-위의 알고리즘은 사실상 DFS 와 동일하다.

 

 

 

2. 색칠 문제

-그래프의 색칠 문제 또한 백트래킹 알고리즘을 활용해 문제 해결이 가능하다.

-구역이 나뉘어져있는 지도가 총 6개의 구역이 존재한다고 해 보자. 각 구역들을 정점 하나로 표현하고, 인접한 구역끼리 간선으로 연결한 그래프가 존재한다.

-색칠 문제는 k개의 색상을 활용하여 인접한 정점은 같은 색상이 칠해지지 않도록 그래프를 칠할 수 있는지의 여부를 묻는다.

#i: 정점, c:색
#질문: 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색상 c로 칠하려면 k개의 색으로 충분한가?

kColoring(i, c):
	if(valid(i,c)):
    	c=color[i]
        if(i=n): result=TRUE
        else:
        	result=FALSE
            d=1
            while(result==FALSE and d<=k):
            	result=kColoring(i+1, d)
                d++
        return result
    else return FALSE

-위의 알골즘은 k개의 색상으로 그래프를 칠할 수 있는지 체크하는 백트래킹 알고리즘이다.

-칠해야할 정점의 총 수는 n이다. 최초의 kColoring(1,1)을 호출한다. kColoring(i,c)를 호출하는 시점에는 정점 1부터 i-1까지 k개 또는 그 이하의 색상으로 칠해져있는 상태인 것이다. 이 상태에서 백트래킹 알고리즘은, 정점 i에 색상 c를 칠하고 끝까지 잘 마무리할 수 있는지를 조사하는 알고리즘이다.

-우선 정점 i에 색상 c를 칠하면 지금까지 칠해놓은 정점들과 색이 충돌하지 않는지 체크한다.

-이를 위해서는 정점 i에 인접하면서 이미 색칠된 정점 중 색상 c로 칠해진 정점이 있는지 확인하면 되는 문제이다.

-valid(i,c)가 이 일을 한다. 이 단계를 통과하면 다음 과정을 진행한다.

-정점 i가 마지막 정점이면 성공적으로 완료되었음을 선언한다(이것은 i가 n번째 칠이 된 정점인 경우임)

-정점 i가 마지막 정점이 아니면, 다음 정점을 하나 선택해 색상을 하나씩 칠해보는 과정을 반복한다.