인생자취

1. 들어가기지난 글에 이어 그래프 탐색 알고리즘에 대해서 다뤄볼 것이다. 이번 글에서는 너비 우선 탐색(BFS;Breadth First Search)을 다뤄보겠다. 너비 우선 탐색은 시작 점으로부터 트리와 가까운 꼭짓점을 모두 탐색한 뒤, 먼 꼭짓점까지 확장하는 규칙을 가지고 있다. 이와 관련해서 좀 더 자세하게 알아보자. 2. 너비 우선 탐색너비 우선 탐색은 시작점으로부터 인접한 꼭짓점을 모두 탐색하고, 인접한 꼭짓점을 시작으로 다시 인접한 꼭짓점들을 탐색하는 탐색이다. 다시 말하면, 깊이가 1씩 증가함에 따라 시작점과 가장 가까운 노드들을 모두 탐색하는 기법이라고 볼 수 있다. 깊이 우선 탐색의 시작점을 기준으로 최대 깊이를 우선으로 탐색하는 기법과는 대조적이다. 너비 우선 탐색도 예시를 통해 알아..

1. 들어가기 지난 글에서는, 그래프에 표시된 모든 노드를 탐색하는 방법으로 시작점을 기준으로 가장 먼 곳을 탐색하는 방법인 DFS를 살펴봤다. 필자는 이번 글에서 DFS를 베이스로 하여, N-Queen 문제를 통해 백트래킹을 적용하는 방식을 살펴볼 것이다. DFS로 완전탐색을 하지만, 백트래킹을 통해 탐색의 필요 여부를 따져볼 수 있다. 탐색의 필요 여부는 다음 예에서 확인해 볼 경우로 계산만 해봐도 뚜렷하게 알 수 있다. 5X5 체스판에 퀸이 놓일 수 있는 경우를 계산한다면, 모든 경우의 수는 5^5 가지가 되는데, 백트래킹으로 조건을 둔다면, 필요하지 않은 경우에 대해서는 더 따져볼 필요가 없게 된다. 그래서 경우의 수가 위의 값 보다는 확연하게 줄어들게 된다. 이와 관련해서 더 자세하게 살펴보도록..