알고리즘 공부하면서 정말 많이 접했었고 들었던 용어가 바로 DFS와 BFS이다.
대충 어떤 차이가 있는지는 알겠고 어떻게 동작하는지도 알겠는데 막상 문제를 풀어보려니 막막해서 정리하게 되었다.
· DFS (Depth First Search) : 깊이 우선 탐색
정의
트리나 그래프에서 한 경로로 최대한 깊숙이 탐색하다가 다시 돌아와 다른 경로로 탐색하는 과정이다.
한 경로의 탐색이 끝나면 다시 이전 과정으로 돌아가 다른 경로로 탐색을 반복하므로 스택이나 재귀를 사용하여 구현하는 경우가 일반적이다.
알고리즘
루트 노드부터 탐색을 시작해 처음 경로의 끝까지 갔다가(2 → 3) 다시 돌아와 다음 경로로의 탐색(4 → 5 → 6) 의 과정을 반복한다.
장/단점
현 경로상의 노드만을 기억하면 되므로 저장 공간의 수요가 비교적 적지만, 한 경로가 무한히 깊을 경우 오버플로우가 발생할 수 있다. 이를 방지하기 위해 깊이에 제한을 두고 구현한다.
깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 가장 최근의 부모 노드로 돌아가(Backtraking) 다른 경로를 선택해 진행한다.
또한 목표 노드에 도달하지 못할 가능성이 존재하며, 도달한다 해도 해당 경로가 최단 경로라는 보장이 없다.
· BFS (Breadth First Search) : 너비 우선 탐색
정의
트리나 그래프에서 루트 노드부터 탐색을 시작해 인접한 모든 노드를 탐색해 나가는 방법이다.
탐색해야 될 노드들을 저장해 놓고 하나씩 탐색해 나가면서 지우는 방식으로 큐를 이용해 구현하는 경우가 일반적이다.
알고리즘
루트 노드부터 탐색을 시작해 인접한 노드들(2,3,4)의 탐색을 마치고 다음으로 인접한 노드들(5,6,7,8)의 탐색을 이어서 진행해 나간다.
장/단점
해가 존재한다면 무조건 찾을 수 있는 방법이지만
경로가 긴 경우 저장 공간의 수요가 매우 커지게 되며 해가 존재하지 않는 경우 모든 노드의 탐색을 마친 후에 실패로 끝나게 된다.
알고리즘의 활용
프로그래머스 - 타겟 넘버
https://programmers.co.kr/learn/courses/30/lessons/43165
numbers의 첫 번째 원소부터 시작해 다음 노드를 하나씩 빼거나 더해가면서 맨 마지막에 target이 되는 경우의 수를 카운트하는 문제로 DFS를 사용하기에 적합
백준 - 로또
https://www.acmicpc.net/problem/6603
프로그래머스 - 단어 변환
https://programmers.co.kr/learn/courses/30/lessons/43163
다음으로 탐색할 노드들을 저장해 놓고 하나씩 탐색해 나가면서 지워 나가는 문제로 BFS 사용 적합
