[Algorithm] DFS(Depth-First Search)

1. 개요

코딩 테스트 문제를 푸는데 DFS에 관련한 문제들이 나왔다. 처음에는 DFS와 관련된 문제인지 모르기도 했고, 시간이 오래걸릴 것 같아 재귀 방식으로 구현을 하기가 싫어서 다른 방식을 고민하다가 결국에는 재귀 방식으로 해결하게 되었는데, 생각보다 측정된 시간이 그렇게 오래 걸리지도 않았고 오히려 다른 방식으로 하던 것의 시간이 더 오래 걸린 것을 보고 재귀 방식도 쓰기 나름이라는 생각이 들었고, 대표적으로 재귀 방식으로 구현하는 알고리즘인 DFS에 대해 좀 더 자세히 알아보게 되었다.

2. DFS

DFS란?

그래프나 트리에서 시작 노드에서 깊이를 우선으로 하여 자식 노드들을 순서대로 탐색하는 알고리즘

• 현재 노드에서 시작해 자식 노드로 계속해서 파고들며 탐색(깊이 우선) ㅡ> 더 이상 파고들 노드가 없다면 반환
• 그래프의 모든 노드 방문
• 역추적(Backtracking)에 적합 ㅡ> 모든 경로를 탐색하면서 막히면 되돌아가기 때문에 경로 찾기 문제에 유용
• 스택 활용 ㅡ> 재귀 호출
• 2가지 방식으로 구현 가능
  • 재귀(Recursive) 방식 ㅡ> 함수 호출을 통해 스택을 활용
  • 반복(Iterative) 방식 ㅡ> 명시적인 스택 활용
• 시간 복잡도: O(V+E) (V:노드의 개수, E: 모든 간선의 개수)

DFS 코드

(프로그래머스: https://school.programmers.co.kr/learn/courses/30/lessons/43165)

#include <string>
#include <vector>

using namespace std;

int answer=0;

void Sum(int index,vector<int> numbers, int target, int total)
{
    if(index==numbers.size())
    {
        if(total==target)
        {
            ++answer;
        }
        return;
    }
    Sum(index+1,numbers,target,total+numbers[index]);
    Sum(index+1,numbers,target,total-numbers[index]);
}

int solution(vector<int> numbers, int target) {
    Sum(0,numbers,target,0);
    return answer;
}

문제를 간단히 설명하면 음이 아닌 정수들이 여러개 주어지고 해당 숫자들의 부호를 '+', '-' 중에 선택해서 목표로 주어진 숫자를 만드는 방법의 개수를 구하라는 것이다. 결국 문제에서 요구하는 것은 주어진 숫자들을 이용해 목표 숫자를 만드는 방법의 수이니 모든 경로를 한 번 탐색해 볼 필요성이 있기 때문에 DFS를 활용하여 해결하기 적합하다.

나는 Sum이라는 이름의 함수를 재귀적으로 호출해 스택을 활용하는 방식으로 DFS를 구현했다. 코드를 보면 Sum에 index라는 현재 몇번째 숫자를 탐색하고 있는지를 알려주기 위한 인자를 증가시키면서 마지막 숫자에 도달하면 목표 숫자를 만들 수 있는 경로였는지를 확인하면서 함수를 반환한다. 또한 깊이를 우선으로 마지막 숫자에 도달하기 전까지 재귀적으로 Sum을 호출하여 해당 경로의 끝을 확인하고 돌아와 다른 경로를 탐색하는 방식으로 구현했다.

3. 정리

코딩 테스트 문제를 풀면서 느끼는 점은 내가 배웠던 알고리즘들을 적용해 다양한 문제들을 푸는 과정에서 알고리즘의 작동 방식이나 구현 방식이 체득이 되고 있다는 것이다. 이론적으로는 알아도 막상 코드로 구현하는 과정에서는 어려움을 겪기 마련이기 때문에 역시 이론을 이해한 뒤에는 실제로 구현하는 과정이 뒤따라 주는 것이 바람직한 것 같다.

DFS를 활용해 문제를 해결하고 나서 느낀 것은 재귀 방식을 이용한 구현이 무조건적으로 나쁜 것은 아니라는 것이다. 원래는 재귀적으로 함수를 호출해서 구현하는 방식들은 안 좋다는 인식이 있어 지양해 왔는데, 막상 반복문으로 문제를 해결하려고 했을 때보다 재귀 방식의 DFS를 활용하여 문제를 해결했을 때의 실행 시간이 훨씬 적었기 때문에 확실히 체감했다. 알고리즘을 확실히 이해하고 적절한 곳에 활용할 수 있는 능력을 키우도록 노력해야겠다.

---

참고자료

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

https://olrlobt.tistory.com/35

[알고리즘] DFS (Depth-First Search) : 깊이 우선 탐색 알고리즘이란?