DFS(Depth First Search)

DFS란 깊이 우선 탐색이라는 의미로 트리나 그래프에서 한 루트로 탐색하다 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 돌아가 다른 루트로 탐색하는 방식이다. 일반적으로 재귀호출을 사용하여 구현하지만 단순한 스택 배열로 구현하기도 한다.

갈림길이 나타날 때마다 다른길이 있다는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 갈림길까지 돌아가면서 이 길은 아님이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료된다.

👍장점
- 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있을 경우 결과물을 빨리 구할 수 있다.

👎단점
- 결과물이 없는 경로에 깊이 빠질 가능성이 있다.
- 얻어진 결과물이 최단 경로가 된다는 보장이 없다. 깊이 우선 탐색은 결과물에 다다르면 탐색을 끝내버리므로 얻어진 결과물이 최적이 아닐 수 있다.
나무위키

사실 무슨 의미인지 정확히 파악하기 어렵지만

일단 오늘의 코플릿 문제를 살펴보자

 

🏋🏽문제

임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색을 합니다.

이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야합니다.

 

🔍나의 풀이

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let result = []

  let traverse = function(node) {
    result.push(node.value)
    node.children.map((child)=>traverse(child))
  }

  traverse(node)
  
  return result
};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
  this.children.push(child); 
  return child;
};

 

DFS이해를 위해 입출력 예시를 먼저 보자

 

let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);
console.log(output); // --> [1, 2, 4, 5, 3]

 

 

1. Node 생성자 함수로 노드객체를 만들어준다.

2. Node객체는 value와 children 프로퍼티를 가진다.  addChild 메소드를 사용해서 자식 노드를 추가할 수 있다.

3. 위 코드를 그림으로 나타내면 아래와 같다.

 

다시 풀이로 돌아가서 설명을 하자면

dfs 함수는 traverse 함수를 호출한다.

traverse 함수는 재귀적으로 현재 노드의 자식 노드를 방문한다.

 

첫 번째 노드인 root의 값을 result 배열에 추가한 후

result.push(node.value);

root의 자식 노드들에 대해 재귀적으로 traverse 함수를 호출한다.

node.children.map(child => traverse(child));

traverse(rootChild1)함수가 호출되면

rootChild1 의 값인 1을 result 배열에 추가한다.

 

rootChild1의 자식 노드들에 대해서 재귀적으로traverse함수호출

rootChild1의 자식노드는leaf1,leaf2

 

traverse(leaf1)함수가 호출되면leaf1의 값인 4를 배열에 추가한 후

leaf1의 자식 노드가 없으므로 함수를 종료한다.

traverse(leaf2)도 같은 방식으로 동작한다.

 

다음으로traverse(rootChild2) 함수가 호출되면

rootChild2의 값인 3을 배열에 추가하고

rootChild2의 자식 노드가 없으므로 함수를 종료한다.

 

그리고 나서 dfs 함수는 result 배열을 반환한다.

마무리

한 2주전에 알고리즘 스터디를 참관한 적이 있는데 그때 주제가 DFS, BFS였다. 머나먼 이야기 같았는데 이렇게 코플릿 문제로 만나게 되어서 당황스러웠지만 덕분에 알아볼 기회가 생겨서 다행이다! 유튜브랑 블로그글들을 아무리 봐도 아직 노드의 개념이 와닿진 않지만 (물론 모든 개념들이 추상적이지만) 문제를 통해 아주 약간의 감은 잡았다. BFS도 나중에 따로 공부해서 둘의 차이점을 비교해봐야겠다.