👨‍💻 사건

코딩테스트 준비하기 앞서, DFS 에 대한 개념을 잡고자 테스트 해보았다.

✅ 해결

• 코드

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"],
};

// (graph, 시작 정점)
const dfs = (graph, startNode) => {
  let needVisitStack = []; // 탐색을 해야 할 노드들
  let visitedQueue = []; // 탐색을 마친 노드들

  needVisitStack.push(startNode);

  // 탐색을 해야 할 노드가 남아 있다면
  while (needVisitStack.length !== 0) {
    const node = needVisitStack.pop();
    console.log("노드:",node)
    if (!visitedQueue.includes(node)) {
      visitedQueue.push(node);
        console.log('방문한 큐',visitedQueue)
      needVisitStack = [...needVisitStack, ...graph[node]];
        console.log("방문해야할 스택",needVisitStack)
        console.log("-----------------");
    }
      console.log("-----------------");
  }

  return visitedQueue;
};

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

• 결과

탐색할 노드: A
방문한 큐 ['A']
방문해야할 스택 (2) ['B', 'C']
-----------------
-----------------
탐색할 노드: C
방문한 큐 (2) ['A', 'C']
방문해야할 스택 (5) ['B', 'A', 'G', 'H', 'I']
-----------------
-----------------
탐색할 노드: I
방문한 큐 (3) ['A', 'C', 'I']
방문해야할 스택 (6) ['B', 'A', 'G', 'H', 'C', 'J']
-----------------
-----------------
탐색할 노드: J
방문한 큐 (4) ['A', 'C', 'I', 'J']
방문해야할 스택 (6) ['B', 'A', 'G', 'H', 'C', 'I']
-----------------
-----------------
탐색할 노드: I // 방문한 큐에 존재
-----------------
탐색할 노드: C // 방문한 큐에 존재
-----------------
탐색할 노드: H
방문한 큐 (5) ['A', 'C', 'I', 'J', 'H']
방문해야할 스택 (4) ['B', 'A', 'G', 'C']
-----------------
-----------------
탐색할 노드: C // 방문한 큐에 존재
-----------------
탐색할 노드: G
방문한 큐 (6) ['A', 'C', 'I', 'J', 'H', 'G']
방문해야할 스택 (3) ['B', 'A', 'C']
-----------------
-----------------
탐색할 노드: C // 방문한 큐에 존재
-----------------
탐색할 노드: A // 방문한 큐에 존재
-----------------
탐색할 노드: B
방문한 큐 (7) ['A', 'C', 'I', 'J', 'H', 'G', 'B']
방문해야할 스택 (2) ['A', 'D']
-----------------
-----------------
탐색할 노드: D
방문한 큐 (8) ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D']
방문해야할 스택 (4) ['A', 'B', 'E', 'F']
-----------------
-----------------
탐색할 노드: F
방문한 큐 (9) ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F']
방문해야할 스택 (4) ['A', 'B', 'E', 'D']
-----------------
-----------------
탐색할 노드: D // 방문한 큐에 존재
-----------------
탐색할 노드: E
방문한 큐 (10) ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']
방문해야할 스택 (3) ['A', 'B', 'D']
-----------------
-----------------
탐색할 노드: D // 방문한 큐에 존재
-----------------
탐색할 노드: B // 방문한 큐에 존재
-----------------
탐색할 노드: A // 방문한 큐에 존재
-----------------
(10) ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']