201222 _ 알고리즘 / DFS/BFS

[토이7]

treeDFS

문제
임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.

입력
인자 1 : node
'value', 'children' 속성을 갖는 객체 (Node)
'node.value'는 number 타입
'node.children'은 Node를 요소로 갖는 배열

출력
배열을 리턴해야 합니다.
주의사항
생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다.

---

정답

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  
  let values = [node.value]; // values = [1] 탐색 시작 노드
  node.children.forEach((n) => { // node의 자식노드의 el을 하나씩 
    // ParentNode.children
    // ParentNode의 속성 children은 호출된 요소의 모든 자식 노드의 elements를 담고있는 실시간 HTMLCollection을 반환
    values = values.concat( dfs(n) ); // concat(재귀함수)를 사용해서 하나씩 붙여
  });
  return values;
};

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

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

// this
// children
// addchildren

Array.prototype.forEach( )

• arr.forEach( callbackfunc )

• 주어진 함수를 해당 배열 요소 각각에 대해 실행함 / map이랑 비슷 (map은 결과값을 배열에 담아준다)

let arr = ["a", 2, "ddd", true]
arr.forEach( (el) => console.log(el) )
// a,2,ddd,true

---

DFS/BFS : 그래프 탐색 알고리즘 ⭐️중요⭐️

• 탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
  

스택 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 / 입구만 뚫려있음

큐 자료구조

• 먼저 들어온 데이터가 먼저 나가는 형식 (선입선출)의 자료구조 / 입,출구가 모두 뚫려있음

재귀함수

• 자기 자시을 다시 호출하는 함수
• DFS를 실질적으로 구현할 때 자주 사용됨
• 종료 조건을 명시해야 함 (그렇지 않으면, 무한 루프에 빠짐)
• 컴퓨터가 함수를 연속적으로 호출하면, 컴퓨터 메모리 내부의 stack프레임에 쌓임. 따라서 stack을 사용해야 할 때, 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많음
• 팩토리얼(!)도 재귀 예
• 최대공약수(가장 큰 공통으로 나눌 수 있는 수) 계산 (유클리드 호제법)
  • 최대공약수
    • 6 / 8 => 2
      • 6의 약수 : 1,2,3,6
      • 8의 약수 : 1,2,4,8
    • 18 / 24 => 6
      • 18의 약수 : 1,2,3,6,9,18
      • 24의 약수 : 1,2,3,4,6,8,12,24
  • 두 자연수 a,b에 대해 (a>b) a를 b로 나눈 나머지를 r이라고 하자.
  • 이때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

function 최대공약수 (a,b) {
    if(a%b === 0) {
      return b
    } else {
      return 최대공약수 (b, a%b)
    }
}
최대공약수 (24,18)

DFS (Depth-First-Search / 깊이우선탐색)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

• 스택자료구조 or 재귀함수를 이용
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다 (방문기준 : (보통) 번호가 낮은 인접 노드부터 시작)
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다
3. 더이상 2의 과정을 수행할 수 없을 때까지 반복한다.

  • 탐색순서 : 1 > 2 > 7 > 6 > 7 > 8 > 7 > 2 > 1 > 3 > 4 > 3 > 5
  • 1부터 스택에 삽입

graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]
visited = [false]*9
function dfx(graph, v, visited) {
  // 현재 노드를 방문 처리
  visited[v] = true; //??
  return(v, end=" ") //??
  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v] {
    if(! visited[i])
      dfs(graph, i, visited)
  }
}
df(graph, 1, visited)

---

출처 : 동빈나님 유튜브 💚️