아직 헷갈렸던 DFS(깊이 우선 탐색)

저번 알고리즘 문제를 BFS로 풀어낸 다음 DFS는 따로 공부를 진행했다.

javascript로는 대부분 재귀 함수를 이용한 모습이 많았는데 아래 코드는 1부타 시작해 연결된 모든 점을 방문하여 순회하는 코드이다.

// 그래프 정보
const graph = {
  1: [2, 3],
  2: [1, 4, 5],
  3: [1],
  4: [2],
  5: [2]
};

// 방문한 정점을 저장할 배열
const visited = [];

function dfs(node) {
  visited.push(node);  // 현재 정점을 방문한 것으로 처리
  for (let i = 0; i < graph[node].length; i++) {
    const nextNode = graph[node][i];
    if (!visited.includes(nextNode)) {  // 다음 정점을 방문하지 않은 경우
      dfs(nextNode);  // 다음 정점으로 이동
    }
  }
}

dfs(1);  // 1 -> 2 -> 4 -> 5 -> 3
console.log(visited);  // [1, 2, 4, 5, 3]