[Algorithm] DFS - 깊이 우선 탐색

목표

---

• Greedy, Dijkstra, DP 알고리즘과 같이 대표적인 알고리즘 중 하나인 DFS 그래프 탐색 알고리즘에 대해 이해하고 학습한다.

 

 

DFS(Depth First Search)란

---

DFS(Depth First Search)

• DFS란 초기 노드에서 시작하여 해를 찾을때까지 자식 노드를 계속해서 타고 들어가며 탐색하는 완전탐색 알고리즘이다. 깊이(Depth)의 노드를 우선적으로 탐색하는 BFS와 반대되는 개념이라고 생각하면 이해하기 쉽다. DFS는 Stack 또는 재귀를 이용해 구현할 수 있는데 재귀를 이용해 구현하는것이 일반적이다. BFS에 대한 개념이 부족하다면 아래 글을 읽고 오면 좋다.

https://zzzzseong.tistory.com/22

[Algorithm] BFS - 넓이 우선 탐색

 

 

• DFS는 목표 노드에 도달할때까지 탐색을 진행하는데 External Node(자식이 없는 노드)를 만나 더 이상 아래로 진행할 수 없다면, 백트래킹을 이용해 다른 노드를 다시 탐색한다. 아래 트리를 이용해 DFS 알고리즘을 이해해보도록 하자.

 

• DFS 알고리즘을 진행하는 탐색 방향은 그래프에 저장된 노드의 순서대로 탐색을 진행한다. 해당 예시에서는 왼쪽 자식노드가 오른쪽 자식노드보다 앞에 있다고 가정한다. 초기 노드 1에서 시작해 4의 값을 가지는 목표 노드를 찾아보자.

 

• 그래프상에서 2번 노드가 4번 노드보다 먼저 위치하기 때문에 2번 노드로 위치를 이동한다. 아쉽게도 2번 노드는 목표노드가 아니기때문에 더 깊이 탐색해야한다.

 

• 9번 노드와 13번 노드 또한 위와 같이 9번 노드가 먼저 위치하기 때문에 9번 노드로 위치를 이동한다. 이제 이 글을 읽으시는 분들도 DFS가 어떤 방식으로 동작하는 알고리즘인지 어느정도 감을 잡을 수 있을 것이라 생각한다.

 

• 9번 노드 또한 목표 노드가 아니기 때문에 11번 노드로 현재 위치를 이동하는데 문제가 발생한다. 더 이상 아래로 내려갈 수 있는 방법이 없다는 것이다. 이때, 백트래킹이라는 개념이 동작한다. DFS에서 백트래킹은 지나온 노드로 돌아가면서 다시 아래로 진행 가능한 노드가 있는지 찾는 과정을 의미한다.

 

• 본인도 처음에 백트래킹이라는 단어를 접하고 복잡한 기능을 추가적으로 구현해야하는것인지 알았지만 진짜 별거없다. 단순히 아래 그림과 같이 진행 가능한 노드가 있을때까지 이전 노드로 돌아가는 과정을 반복하는 것이다. 심지어 DFS를 재귀로 구현하는 것이라면 for문과 return 하나로 백트래킹이 가능해진다.

 

• 이후로의 과정은 지금까지의 과정을 반복하는 것이기 때문에 설명은 생략하고 목표노드를 찾을때까지 그림으로만 과정을 설명하겠습니다. 

 

 

 

 

DFS(Depth First Search) Code

---

• 개인적인 생각으로는 DFS는 활용 방안이 매우 다양하기 때문에 특정 알고리즘처럼 DFS 문제를 마주했을때는 이렇게 풀어라! 라고 할 수 있는 코드를 제시하기가 어렵다. 그렇기에 DFS가 가장 기본적이고 유명한 알고리즘이 아닐까 싶다. 그렇다고 아무런 코드도 작성하지 않으면 서운하니까 그냥 앞서 설명한 그래프 예제를 코드로 구현해서 올려보았습니다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    private static final Map<Integer, List<Integer>> graph = new HashMap<>();

    public static void main(String args[]) {
        init();

        //초기 노드 1, 재귀를 이용한 dfs 시작
        dfs(1);
    }

    public static void dfs(int n) {
        System.out.println("현재 위치: " + n);

        //n번 노드에서 도달 가능한 node list
        List<Integer> nextNodes = graph.get(n);

        //도달 가능한 node가 있다면 방문
        for (Integer nextNode : nextNodes) {
            //n번 노드에서 도달 가능한 노드의 값이 4라면 탐색 종료
            if(nextNode == 4) {
                System.out.println("목표노드 도달: " + nextNode);
                return;
            }

            //목표 노드에 도달하지 못했고, 아래에 도달 가능한 노드가 있다면 재귀(아래 방향으로 탐색)
            dfs(nextNode);
        }
    }

    public static void init() {
        //정점의 갯수(9)만큼 graph 초기화
        graph.put(1, new ArrayList<>());
        graph.put(2, new ArrayList<>());
        graph.put(4, new ArrayList<>());
        graph.put(9, new ArrayList<>());
        graph.put(13, new ArrayList<>());
        graph.put(5, new ArrayList<>());
        graph.put(8, new ArrayList<>());
        graph.put(11, new ArrayList<>());
        graph.put(12, new ArrayList<>());

        //간선의 갯수(8)만큼 graph 초기화
        graph.get(1).add(2);
        graph.get(1).add(4);
        graph.get(2).add(9);
        graph.get(2).add(13);
        graph.get(4).add(5);
        graph.get(4).add(8);
        graph.get(9).add(11);
        graph.get(9).add(12);
    }
}