알고리즘: 깊이 우선 검색

트리 및 그래프 순회는 코딩 인터뷰에서 인기 있는 주제입니다. 그래프 순회에 대한 많은 접근 방식이 있지만 가장 일반적이고 친숙해야 할 중요한 것 중 하나는 깊이 우선 검색(DFS)입니다. 알고리즘의 기본 아이디어와 몇 가지 구현 예를 살펴보겠습니다.

기본 사항

깊이 우선 검색은 그래프 데이터 구조를 순회하는 데 사용되는 알고리즘입니다. 노드를 방문하는 순서입니다. 이름에서 알 수 있듯이 순회는 깊이 우선 방식으로 수행됩니다. 즉, 특정 노드에서 시작하여 추가 노드를 탐색하기 전에 해당 노드로 최대한 깊이 순회합니다. 리프 노드(자식이 없는 노드)가 발견되면 완전히 탐색되지 않은 노드가 발견될 때까지 역추적이 발생하고 거기서부터 깊이 우선 방식으로 검색이 계속됩니다.

트리 순회 순서

루트 노드(6)에서 시작하여 트리의 왼쪽을 최대 깊이까지 탐색한 후 오른쪽을 탐색합니다. 이 논리는 자식 노드에서도 계속됩니다. 노드 8에서 왼쪽(8 -> 1 -> 3)이 오른쪽(8 -> 7)보다 먼저 탐색됩니다.

트리가 아닌 순회 순서

DFS는 트리가 아닌 구조에서도 사용할 수 있습니다. 탐색 순서는 시작 노드와 탐색 논리에 따라 변경될 수 있지만 개념은 여전히 ​​유효합니다. 추가 노드를 탐색하기 전에 모든 자식 노드를 최대 깊이까지 탐색합니다.

구현

DFS 알고리즘은 데이터 구조를 사용하여 재귀적으로 또는 반복적으로 구현될 수 있습니다. 재귀 구현은 호출 스택을 활용하는 반면 반복 솔루션은 스택을 직접 사용합니다. 그래프를 순회하는 동안 노드가 스택에 추가되고 완전히 탐색되면 제거됩니다.

참고: 재귀 구현은 시각적으로 더 우아하고 구현하기 간단하기 때문에 DFS에서 더 일반적인 경향이 있습니다.

문제

경로 값의 합이 주어진 값 "k"와 동일한 루트에서 리프 경로가 있는지 확인하는 알고리즘을 작성하십시오.

class Node {
  constructor(val) {
    this.val = val
    this.left = null
    this.right = null
  }
}

솔루션 - 재귀

const hasPath = (node, k) => {
  if (node === null) return false

  if (node.left === null && 
      node.right === null && 
      node.val === k) {
        return true
  }
  return hasPath(node.left, k - node.val) || 
         hasPath(node.right, k - node.val)
}

솔루션 - 반복

const hasPath = (node, k) => {
  const stack = [ [node, k ] ]

  while (stack.length > 0) {
    const [ node, target ] = stack.pop()

    if (node.left === null && node.right === null && node.val === target) {
      return true
    }

    if (node.right) {
      stack.push([node.right, target - node.val])
    }

    if (node.left) {
      stack.push([node.left, target - node.val])
    }
  }
  return false
}