DFS 깊이 우선 탐색

그래프 탐색은 한 정점에서 차례대로 모든 정점을 방문하는 것

깊이 우선 탐색(Depth First Search)은 그래프 탐색방법 중 하나이다.

동작 방식은 다음 노드(node)를 탐색하기 전에 해당 분기(branch)를 끝까지 깊이 탐색하는 것이다.

DFS의 구현은 일반적으로 재귀호출을 사용하여 선입후출(FILO) 방식으로 구현한다.

스택을 사용하여 구현할 수도 있지만 결과 코드는 재귀호출이 더 깔끔하다고 한다.

구현 알고리즘은 다음과 같다.
재귀호출을 사용하는 방법
1. 시작 노드를 방문처리(visited)
2. 해당 노드와 인접한 노드 중 하나를 시작 노드로 하여 다시 DFS탐색(재귀호출)
3. 방문하지 않은 인접노드가 없다면 종료(return)한다.

스택을 사용하는 방법
1. 시작 노드를 스택에 삽입
2. 스택에서 노드 하나를 꺼내서(popup) 방문처리(visited)
3. 해당 노드와 인접한 노드 중 하나를 스택에 삽입(push)
4. 방문하지 않는 인접노드가 없다면 종료(return)한다.
5. 2~4번을 반복하다가 모두 방문처리 되어 스택이 비면 탐색을 종료한다.

이 알고리즘을 사용하는 경우

• 모든 노드를 방문해야할 때
  
  

입출력 예

         A
      /     \
     B       C
    / \      /\
   D  E     F  G
  /\  /\   /\  /\
 H I J K  L M  N O

출력순서
A - B - D - H - I - E - J - K - C - F - L - M - G - N - O

예시 코드

• 그래프 데이터

// ['노드', '연결된 노드']
const dfsArr = [
  ['A', 'BC'],
  ['B', 'ADE'],
  ['C', 'AFG'],
  ['D', 'BHI'],
  ['E', 'BJK'],
  ['F', 'CLM'],
  ['G', 'CNO'],
  ['H', 'D'],
  ['I', 'D'],
  ['J', 'E'],
  ['K', 'E'],
  ['L', 'F'],
  ['M', 'F'],
  ['N', 'G'],
  ['O', 'G'],
];
solution(dfsArr);

• 재귀호출

const solution = (arr) => {
  const answer = 'ABDHIEJKCFLMGNO';
  /** DFS: 깊이 우선 탐색
   *           A
   *        /    \
   *      B       C
   *    /  \    /  \
   *   D   E   F   G
   *  /\  /\  /\  /\
   * H I J K L M N O
   * A-B-D-H-I-E-J-K-C-F-L-M-G-N-O
   */
  // 인접리스트 생성
  const obj = arr.reduce((acc, cur) => {
    acc[cur[0]] = cur[1];
    return { ...acc };
  }, {});
  // console.log(obj);

  // 재귀호출을 이용해서 순서대로 출력
  const visited_dfs = [];
  const dfs = (node) => {
    if (!visited_dfs.includes(node)) visited_dfs.push(node);
    const adjNodes = obj[node].split('');
    for (let i = 0; i < adjNodes.length; i++) {
      if (!visited_dfs.includes(adjNodes[i])) dfs(adjNodes[i]);
    }
  };
  // 시작노드
  dfs('A');
  console.log(visited_dfs.join('') === answer);
};

• 스택

const solution = (arr) => {
  const answer = 'ABDHIEJKCFLMGNO';
  /** DFS: 깊이 우선 탐색
   *           A
   *        /    \
   *      B       C
   *    /  \    /  \
   *   D   E   F   G
   *  /\  /\  /\  /\
   * H I J K L M N O
   * A-B-D-H-I-E-J-K-C-F-L-M-G-N-O
   */
  // 인접리스트 생성
  const obj = arr.reduce((acc, cur) => {
    acc[cur[0]] = cur[1];
    return { ...acc };
  }, {});
  // console.log(obj);
  // stack 을 이용해서 순서대로 출력해보자
  const stack = [];
  const visited = [];
  stack.push(['A', obj['A']]);
  while (stack.length) {
    const [node, link] = stack.pop();
    if (!visited.includes(node)) visited.push(node);
    const linkedNodes = link.split('');
    for (let i = linkedNodes.length - 1; i >= 0; i--) {
      if (!visited.includes(linkedNodes[i]))
        stack.push([linkedNodes[i], obj[linkedNodes[i]]]);
    }
  }
  console.log(visited.join('') === answer);
};