깊이 우선 탐색(depth-first search, DFS)

깊이 우선 탐색이란?

• 트리에서는 왼쪽 노드부터 확인하여 탐색하지 않은 경우에 왼쪽노드에 넘어가고를 반복하여 마지막 깊이까지 들어간 뒤 마지막 노드의 인접 노드들을 전부 탐색한 뒤 백트래킹을 하며 탐색하지 않은 노드들을 탐색한다.
• 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색.
• 얻어진 해가 최단 경로가 된다는 보장이 없다.
• 탐색 지점에서 일직선으로 탐색을 해나가는 느낌

설명

1. 방문을 체크하는 배열 존재
2. 시작 노드를 설정한 뒤 DFS메서드를 불러오고 시작노드의 방문체크를 true로 바꾼다.
3. DFS메서드에서는 설정한 시작노드의 인접리스트를 읽어온다.
4. 인접리스트중 방문하지 않은 노드가 존재하면 그 노드를 시작노드로 DFS 메서드를 호출한다.(재귀)

예시

코드(Java)

import java.io.*;
import java.util.*;

/* 인접 리스트를 이용한 방향성 있는 그래프 클래스 */
class Graph {
  private int V;   // 노드의 개수
  private LinkedList<Integer> adj[]; // 인접 리스트

  /** 생성자 */
  Graph(int v) {
      V = v;
      adj = new LinkedList[v];
      for (int i=0; i<v; ++i) // 인접 리스트 초기화
          adj[i] = new LinkedList();
  }

  /** 노드를 연결 v->w */
  void addEdge(int v, int w) { adj[v].add(w); }

  /** DFS에 의해 사용되는 함수 */
  void DFSUtil(int v, boolean visited[]) {
      // 현재 노드를 방문한 것으로 표시하고 값을 출력
      visited[v] = true;
      System.out.print(v + " ");

      // 방문한 노드와 인접한 모든 노드를 가져온다.
      Iterator<Integer> i = adj[v].listIterator();
      while (i.hasNext()) {
          int n = i.next();
          // 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
          if (!visited[n])
              DFSUtil(n, visited); // 순환 호출
      }
  }

  /** 주어진 노드를 시작 노드로 DFS 탐색 */
  void DFS(int v) {
      // 노드의 방문 여부 판단 (초깃값: false)
      boolean visited[] = new boolean[V];

      // v를 시작 노드로 DFSUtil 순환 호출
      DFSUtil(v, visited);
  }

  /** DFS 탐색 */
  void DFS() {
      // 노드의 방문 여부 판단 (초깃값: false)
      boolean visited[] = new boolean[V];

      // 비연결형 그래프의 경우, 모든 정점을 하나씩 방문
      for (int i=0; i<V; ++i) {
          if (visited[i] == false)
              DFSUtil(i, visited);
      }
  }
}
/** 사용 방법 */
public static void main(String args[]) {
    Graph g = new Graph(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    g.DFS(2); /* 주어진 노드를 시작 노드로 DFS 탐색 */
    g.DFS(); /* 비연결형 그래프의 경우 */
}

References

https://ko.wikipedia.org/wiki/깊이_우선_탐색

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

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog