DFS(Depth First Search)는 깊이우선 탐색이라고 부른다. 처음 접하시는 분들은 용어 자체가 생소하게 들리기 때문에 풀어서 설명드리겠습니다.
오늘도 어김없이 실생활 예를 들어 설명해보려합니다.
요즘에는 지하철 어플이 잘 되어있어서 출발지와 도착치 그리고 출발 시간만 지정하면 최적의 경로를 찾아줍니다.
하지만 약 15년 전만해도 그렇지 않았습니다. 매일 다니는 길을 제외하면 지하철 노선도를 보면서 어디서 갈아타야하는지
확인했어야하죠. 평생 서울에 살았던 사람들도 그러했는데... 평생 지하철이라곤 타본적도 없는 사람이 버스타고 서울역에
도착해서 도봉구까지 지하철로 최단시간으로 이동하려면 어떻게 해야할까요??
답은 참 간단하면서도 한편으로 무식하지만 서울역에서 도봉구까지 지하철로 갈수 있는 모든 길을 전부 다 가보고 시간이 제일 적은길을 택하면 됩니다.
사람이라면 각 역의 출발시간과 도착시간, 주변사람들에게 물어보기 등등.. 다양한 방법을 통해 답을 얻겠지만 컴퓨터는 그렇지 못합니다. 하지만 컴퓨터는 반복적인 일을 아주 빠르게 잘 수행해내죠.
이렇게 모든 경우를 다 따져보면서 원하는 답을 얻는 방법중 하나가 DFS입니다.
실생활예를 좀더 정형화 된 글로 바꿔보면 다음과 같습니다.
- 한 노드를 방문한다.
- 그 노드와 인접하면서, 아직 방문하지 않은 노드에 방문한다.
- 만약 방문한 노드에서 인접한 다음 노드를 선택할 수 없으면 직전의 방문 노드로 돌아간다.
- 동일한 방법으로 인접한 노드 중 방문하지 않은 노드에 방문한다.
잘 보시면 두번째 줄부터 마지막 줄이 뜻하는게 반복적인 것을 확인하실 수 있습니다.
정리해보자면, 인접한 여러 노드들이 있을 때, 하나의 노드를 선택 후 다음 노드로 이동을 시도한다. 이동하려는 노드가 초기에 설정해준 조건에 부합하면 이동한다. 그러다 더이상 이동가능한 노드가 없으면 이전 노드로 돌아가 아직 가보지 못했지만 갈 수 있는 노드로 이동을 반복한다.
이렇게 확산해나가면 원하는 조건 내에서 모든 경우의 수를 해볼수 있습니다.
글이 길어지기 때문에 코드로 어떻게 다음 글에 이어서 포스팅하겠습니다.
'알고리즘' 카테고리의 다른 글
| [c 알고리즘] DFS 실습 - 정올 (2167번) 책 꺼내기 part1 (0) | 2023.01.12 |
|---|---|
| [c 알고리즘] 1169 정올 주사위 던지기 1 문제 해설 (0) | 2023.01.11 |
| [c 알고리즘] 백준 별찍기 5 (2442번) (2) | 2023.01.07 |
| [c 알고리즘] 백준 별찍기4 (2441번) (0) | 2023.01.07 |
| [c언어 알고리즘] 백준 별찍기3 (2440번) 해설 (0) | 2023.01.06 |
