인생자취

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