[알고리즘] Brute Force Algorithm - DFS

Brute Force Algorithm

• Brute = 무식한, Force = 힘, Algorithm = 해결방법. 즉 한국어로 직역하면 무식하게 힘으로 찾는 알고리즘 기법입니다.
• 조금 더 유식한 말로는 완전탐색 알고리즘이라고 합니다. 나쁘게 말하면 무식하지만, 좋게 말하면 모든 경우의 수를 탐색하기 때문에 절대로 틀릴 수 없는 알고리즘 설계 기법입니다.
• Brute Force Algorithm은 완전 탐색을 하기 때문에 '최적의 해'를 찾기위한 알고리즘 설계 기법이지만, 모든 경우의 수를 다 탐색하기 때문에 상대적으로 느릴 수 있습니다.
• Brute Force Algorithm에는 대표적으로 DFS와 BFS가 있습니다.

 

 

DFS

• Depth First Search의 줄임말로, 한국어로는 '깊이 우선 탐색' 이라고 합니다.
• 이름 그대로 깊게 탐색하면서 답을 찾아 나갑니다. '일단 가보고 아니면 돌아오고~'의 방식으로 탐색을 진행합니다
• 가장 쉽게 이해하기 위해서는 미로를 예시로 들으면 될 것 같습니다.

 

• 말이 시작점에서 끝점을 찾아가야하며 아래, 오른쪽 위, 왼쪽의 우선순위를 가지고 탐색을 합니다.

 

• 말은 시작점에서 아래쪽과 오른쪽으로 이동할 수 있습니다.
• 아래쪽이 우선순위가 더 크기때문에 아래쪽으로 이동합니다. 단, '아래쪽으로 가보고 안되면 돌아와서 오른쪽으로 가야지' 라는 탐색 방식이기 때문에 오른쪽으로 가겠다고 기록을 합니다.
• 이미 탐색한 곳은 탐색이 완료되었으므로 더 이상 탐색을 하지 않겠다는 뜻의 마킹을 합니다.

 

 

 

 

 

• 말이 밑으로 두번을 와서 또 갈림길을 만났습니다. 마찬가지로 오른쪽은 나중에 갈 곳으로 지정을 해두고 밑으로 내려갑니다.

 

 

 

 

 

 

• 말이 어느새 첫 막다른 골목을 만났습니다.
• 더이상 진행할 수 없으므로 왔던길을 되돌아 가야합니다.
• 이 때, 전에 "여기로 가서 막히면 저기로도 가봐야지" 라고 마크 해 놓은 곳까지 되돌아갑니다.

 

 

 

• 체크포인트 까지 와서 오른쪽으로 탐색을 했으나 또 막혔습니다. 그 전의 체크포인트까지 다시 이동합니다.

• 다시 원래 자리로 되돌아와 오른쪽으로 탐색을 시작하고 끝 점을 탐색합니다.
• 여기서 눈치 채셨을수도 있겠지만, 왜 완전 탐색 알고리즘인지에 대해서 알 수 있습니다. 
• 마지막 그림에서 보면 모든 길이 회색으로 칠해졌습니다. 즉 전부 다 탐색 했다는 뜻입니다.
• 이처럼 완전탐색 알고리즘은 해를 찾기 전까지 모든 경우의 수를 탐색합니다.

 

최선의 해 vs 해의 존재 유무

• 대부분의 문제는 두가지로 갈리게 됩니다. 첫번째는 최선의 해를 찾는 경우이고, 두번째는 해가 존재하는가? 에 대해 yes or no로 답하는 문제입니다.
• 최선의 해를 찾는 경우는 미로찾기에서 가장 빠르게 끝에 도달하는 방법을 찾는 것이고, 해가 존재하는지를 찾으려면 일단 어떻게든 끝에 도달하기만 하면 됩니다.
• DFS는 두가지 문제중에서 "해가 존재하는가?" 라는 질문에 조금 더 적합한 알고리즘 기법입니다. 이것 또한 예시를 들어서 설명해보도록 하겠습니다.

• 이번엔 끝 지점이 비교적 가까운 곳으로 바뀌었습니다. 
• 두번째 그림에서 말이 끝지점의 바로 앞까지 도달했습니다. 하지만 밑으로 가는 것이 우선순위이기 때문에, 세번째 그림처럼 밑으로 가는 선택지에서 끝까지 전부 탐색하고 나서야 돌아올 수 있습니다.
• 세번째 그림에서 되돌아와 네번째 그림처럼 끝 지점으로 가면 해를 찾을 수 있습니다.
• 해의 존재 유무를 묻는 문제라면 여기서 알고리즘이 종료됩니다. 하지만 최선 해를, 즉 최단거리로 끝에 도달하는 방법을 찾는 문제라면 여기서 종료되지 않습니다. 누가봐도 저게 가장 빠르고 가까운 해인데 말이죠.

 

 

• DFS알고리즘은 모든 경우의 수를 다 탐색이 끝나고서 전부 비교를 해야 "아! 아까 방법이 최단거리였구나"를 알기 때문에 결국 해를 찾았다 하더라도 다른 가능성을 찾아서 완전 탐색을 수행하게 됩니다.

 

 

 

 

 

마치며...

• 최선의 해를 찾아야 하는 문제에서는 DFS가 비교적 비효율적일 수 있습니다.
• 최선의 해를 찾아야 하는 문제에서 DFS보다 효율적인 BFS라는 것이 존재합니다. 이것은 다음 포스팅에서 다루겠습니다.