깊이우선탐색(DFS)란?
깊이우선탐색 순회는 그래프의 한 정점을 방문한 후, 해당 정점에 인접하면서 방문하지 않은 정점을 선택하면서 탐색하는, 완전 탐색 기법 중 하나이다.
만약 현재 방문한 정점에서 다음 방문 정점을 선택할 수 없다면, 직전의 방문 정점으로 돌아가, 선택을 이어간다.
DFS를 구현하는 방법에는 크게 두 가지가 있다.
첫 번째. 재귀함수를 이용한 구현.
두 번째. 스택을 이용한 구현.
덧붙여 DFS의 시간 복잡도는 O(V+E)이다.
여기서 중요한 포인트는 DFS를 구현할 때, 방문한 노드를 적절하게 체크하거나 종료 조건의 논리성을 확보해야 한다는 것이다.
그렇지 않으면 무한 루프에 빠질 가능성이 있다.
깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.
재귀함수를 이용한 DFS 구현
상단의 코드는, 프로그래머스 Level2에 해당하는 타겟 넘버를 풀이한 dfs함수이다.
인풋값으로 받은 벡터, numbers를 참조형 파라미터로 넘겨서 데이터 복붙에 드는 오버헤드를 줄이고,
인덱스를 이용하여 재귀 탈출 조건을 확인.
이후, sum을 이용하여 재귀 탈출 시에, 요구 조건을 만족하는지 확인하여, 값을 리턴한다.
이렇게 깊이 탐색을 통해서 리턴한 값을 합산하여, 최종적으로 result값을 반환하여, 값을 구한다.
스택을 이용한 DFS 구현
마찬가지로, 스택을 이용해서도 DFS 탐색을 구현할 수 있다.
후입선출(LIFO)이라는 스택 자료구조의 특징을 이용하는데,
-
먼저 시작 노드를 스택에 넣는 것이 초기작업으로 필요하다.
-
스택에서 노드를 꺼낸 후(Pop), 인접 노드를 다시 스택에 삽입(Push)한다. 이때, visited나 그래프의 값을 수정하여, 중복 탐색을 막도록 하기도 한다.
-
스택 자료구조에 값이 없을 때까지 반복문을 통해서 반복한다.
이러한 스택을 이용한 DFS 구현의 경우에는 스택 오버플로우가 발생할 위험이 있는 재귀함수 구현과 다르게, 스택의 크기를 조절하거나 동적으로 확장할 수 있어 스택 오버플로우를 방지할 수 있다.
