[알고리즘] Backtracking 되추적 트리 순회 개념 이해

Backtracking (되추적)

미로와 같이 알 수 없는 곳에서 빠져나오는 가장 단순한 방법은 한쪽 방향으로 계속 탐색하면서 모든 길과 방향을 찾아보는 것입니다.

백트래킹(Backtracking) 은 그래프 또는 트리 등의 자료 구조에서 순서대로 방문해보고 원하는 결과가 나오는지 확인하고 원래 위치로 다시 돌아오는 방법을 의미합니다. 단순하게 모든 데이터를 검색하는 것을 맹목적 탐색(blind search)이라고 부를 수도 있겠지만, 특정 선택이 타당하지 않거나 결실이 없는 것으로 판명될 때 취소후 원래 위치로 복귀하여 다음 순서를 검색하는 방법으로, 다양한 경로(또는 경우의 수)에서 찾고자 하는 문제를 해결하는 데 사용되는 일반적인 알고리즘 기법입니다.

BFS(Breadth-First Search), DFS(Depth-First Search)와 같은 검색 알고리즘과 결합하여 문제의 가능한 모든 경로나 해결책을 탐색하는 데 사용됩니다.
 

Tree traversal (트리 순회)

DFS, BFS 로 알려진 알고리즘을 이해를 돕기 위해서 트리 순회하는 방식에 대해서 살펴보겠습니다. 각 order 의 기준은 Node(Root) 가 되고, Left, Right 어느 쪽을 먼저 탐색할 것인지의 관점입니다. 

 

트리 순회 이해를 돕기 위한 Sample Tree

 

Preorder traversal

전위 순회(Preorder), Depth-First Traversal 라고도 하며, Node 를 방문하고 Left 를 하위까지 모두 탐색 후 Right 하위를 모두 탐색합니다.

Preorder 순회 : E - B - A - D - C - F - I - G - H - J ( root, left, right )
 

Inorder traversal

중위 순회(Inorder) 의 경우, Left 를 하위까지 모두 탐색후, Node 를 방문한다. 그리고 Right 하위를 모두 탐색합니다.

Inorder 순회 : A - B - C - D - F - E - I - H - G - J ( left, root, right )

 

Postorder traversal

후위 순회(Postorder) 의 경우, Left 를 하위까지 모두 탐색후, Right 하위를 모두 탐색 한 후, Node 를 방문합니다.

Postorder 순회 : A - C - F - D - B - H - J - G - I - E ( left, right, root )
 

Level-order traversal

레벨 순서 순회(Level-order) 의 경우, Breadth-First Traversal 이라고도 하며, 낮은 레벨(Root) 부터 차례로  방문합니다.
Level-order 순회 : E - B - I - A - D - G - C - F - H - J

 

 

DFS : Depth-First Search 

깊이 우선 검색시 방문 순서

 

깊이 우선 검색(Depth First Search) 를 의미하며, Leaf 노드(방문하지 않은 이웃이 없는 노드)를 만나거나 목표 상태에 도달하면 이전 노드로 역추적하여 다른 방문하지 않은 분기를 Preorder 로 탐색합니다.

방문하는 도중에 만나는 새로운 Node 의 하위 후손을 먼저 방문하기 위해서는 후입선출(LIFO) 처리가 필요하게 되고, 이것은 DFS 는 재귀적인 호출 또는 Stack 을 사용해서 탐색하게 됨을 의미합니다.

즉, 각 Node 를 만나서 하위 자식 Node 정보를 추가하고, 추가한 하위 자식 Node 부터 검색하는 것입니다.

 

DFS 의 간략한 코드 예를 아래에 추가하였습니다.

void DFS(int now)
{
	int i;

	//! 현재 방문한 곳은 방문 처리 해준다.
	visit[now] = true;
	printf("%c\n",now+65);

	for(i=0; i<GRAPH_SIZE; i++)	{
    	//! 현재 방문한 곳에서 갈수 있고 방문한적이 없으면
		if(a[now][i]==1 && visit[i]==false)
			DFS(i);
	}
}

 

BFS : Breadth-First Search

 

너비 우선 검색시 방문 순서

너비 우선 검색(Depth First Search) 를 의미하며, 다음 단계의 노드로 이동하기 전에 노드의 모든 이웃을 방문하여 그래프를 Level-order 로 탐색합니다.

방문하는 도중에 만나는 새로운 Node 가 있더라도 먼저 확인한 모든 이웃 Node를 먼저 방문하기 위해서는 선입선출(FIFO) 처리가 필요하게 되고, 이것은 BFS 는 Queue 와 같은 FIFO 를 처리할 수 있는 자료 구조를 사용하게 됨을 의미합니다.

 

BFS 의 간략한 코드 예를 아래에 추가하였습니다. (배열 Queue 사용)

void BFS(int start)
{
	int queue[GRAPH_SIZE*GRAPH_SIZE];
	int front,rear,now,i;

	for(i=0; i<GRAPH_SIZE; i++)
		visit[i] = false;

	front = 0;
	rear = 0;
	visit[start] = true;
	queue[front++] = start;
    //! 배열로 선언한 Circular Queue 이다. front > rear 이면 empty
	while (front > rear)
	{
		now = queue[rear++];
		printf("%c\n", now+65);		// 현재 방문한곳 출력		
		for(i=0; i<GRAPH_SIZE; i++) {
            //! // 현재 방문한 곳에서 갈수 있고 방문한적이 없으면
			if(a[now][i]==1 && visit[i]==false)
			{
				visit[i] = true;
				queue[front++] = i;
			}
		}
	}
}

 

Implementation

위에서 언급했듯이 BFS 에서는 Queue 를 사용하고, DFS 에서는 Stack 이나 재귀함수를 사용하게 됩니다.
여기에서는 배열로 Graph 를 선언하고 순회하는 DFS, BFS 함수를 소개합니다.

 

Backtracking 구현시 BFS 와 DFS 의 기본 구조는 유사합니다.

1. 각 노드를 어떻게 방문할 것인가의 관점에서 하위 노드의 정보를 대기열에 넣어주고 모든 곳을 방문합니다.
2. 추가 검색할 노드를 어떻게 관리하느냐에 따라서 순회 방식이 달라지게 되며, 대기열을 Queue 를 통해 관리하는 경우(BFS) 와 Stack (또는 재귀) 를 통해 관리하는 경우(DFS) 로 나뉘게 됩니다.
3. 각 노드를 방문한 다음 visit[ ] 과 같은 방문 처리를 해주어 다시 방문하지 않도록 해야 합니다.
4. 재귀함수를 사용할 경우에는 반드시 빠져나오는 구문을 만들어두어야 합니다.

DFS, BFS 에 대한 상세 설명과 구현 코드는 아래 글에서 소개하고 있으니 참고해주세요.

 

[알고리즘] 깊이 우선 검색 - DFS (Depth-First Search)

[알고리즘] 깊이 우선 검색 - DFS (Depth-First Search)

 

[알고리즘] 너비 우선 검색 - BFS (Depth-First Search)

[알고리즘] 너비 우선 검색 - BFS (Depth-First Search)

 

읽어주셔서 감사합니다.