문제 71. 깊이 우선 탐색

 

 

 

"깊이우선탐색" 이란?

• 목표한 노드를 찾기 위해 가장 우선순위가 높은 노드의 자식으로 깊이 들어갔다가 목표 노드가 존재하지 않으면 처음 방문한 노드와 연결된 다른 노드부터 그 자식 노드로 파고드는 검색방법

 

// 데이터
graph = {
  E: ["D", "A"],
  F: ["D"],
  A: ["E", "C", "B"],
  B: ["A"],
  C: ["A"],
  D: ["E", "F"],
};


// 출력
E D F A C B

 

 

 

 

미리 생각해 봐야할 것

• 순서를 디테일하게 파악

 

• 객체 접근 방식 생각

 

답

let graph = {
  E: ["D", "A"],
  F: ["D"],
  A: ["E", "C", "B"],
  B: ["A"],
  C: ["A"],
  D: ["E", "F"],
};

function dfs(graph, start) { 
  let visited = []; // 빈배열을 만들어준다
  let stack = [start]; // 맨처음 'E' 를 넣어준다

  while (stack.length != 0) { // stack의 길이가 0이 아닐때까지 돈다
    let n = stack.pop(); // stack 의 맨 끝요소를 추출
    // console.log(n)
    if (!visited.includes(n)) { //만약 빈배열(visited)에 stack.pop() 요소가 없다면 --> 출력 E D F A C B 에서 알파벳이 겹치지 않으므로 조건을 넣어준다.
      visited.push(n); 
      let sub = graph[n].filter((x) => !visited.includes(x)); //filter 함수를 사용, graph의 key 값을 참고, value를 탐색하여 visited 배열에 포함되어 있지 않은 새로운 배열을 만들어준다.
      for (let i of sub) {
        stack.push(i);
      }
    }
  }
  return visited;
}

console.log(dfs(graph, "E"));