자바스크립트 코테 핵심로직(2) 탐색 알고리즘 중 DFS를 공부해보자

탐색 알고리즘이란? 

그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 

그럼 그래프는 뭔데?!

그래프란, 자료구조 중 하나이다.

한 나라에는 도시들이 여러개 존재하고 이들은 도로들이 연결지어주고있다. 
이때 이 도시들과 그에 연결된 도로를 합쳐서 자료구조로 만든것이 그래프이다.
정점은 도시들이 되고, 간선은 도로들이 된다.
(근데 왜 1에서는 2, 3만 갈 수 있는걸까..?)

 

제대로된 정의는 다음과 같다.

정점과 간선으로 구성된 한정된 자료구조를 의미하며, 각각의 지점을 정점이라고 한다. 그리고 정점과 정점을 연결시켜 주는 것을 간선이라 부른다.

이런 그래프 자료구조를 탐색하는 것이 DFS(깊이우선탐색), BFS(너비우선탐색)이다.

 

왜 DFS, BFS를 알아야 하는가?

그냥 탐색하면 안되나? 왜 이런 개념을 알아야 하는지?!

1. 한 정점에서 다른 정점으로 연결된건 어떻게 앎?
2. 위의 알고리즘이 없다면 직접 효율적인 코드를 짜야할텐데 할 수 있음?! 그리고 그게 정확하다고 장담 가능??

 

그래프를 탐색하기 위해선 어느정도 효율성, 체계성이 필요하다. 이 말은 DFS, BFS를 공부하다보면 알 수 있다고하니.. 개념을 찍먹해보자.

 

DFS(깊이 우선 탐색) 이란?

시작점에서 갈 수 있는 정점부터 깊이 있게 파고 드는 알고리즘

출처 https://developer-mac.tistory.com/64

 

현재 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점으로 갈 수 있다면 그 정점에 가서 같은 행위를 반복한다. 이때, 방문한 지점은 다시 방문하지 않기 위해 표시를 해둔다.

1. 시작 정점을 1로 설정
2. 1번 탐색 시작 1번과 연결되었고 방문 안한 정점이 어디지? 2번이 있네. 2번으로 가자.
3. 2번과 연결되었고, 방문 안한것? 3번이네. 3번으로 가자.
4. 3번은? 4번이 있네. 4번으로 가자.
5. 4번은? 없는데..?? 그러면 3번으로 다시 올라가자.
6. 3번은? 방문 안한곳이 없네.. 다시 2번... 다시 1번
7. 1번은? 5번이 있네. 5번으로 가자.
-> 이런 식으로 방문 안한 곳이 없을때까지 반복

 

DFS의 장단점

장점: 코드가 직관적이고, 구현하기 쉽다

-> 사실 일정행동을 계속 반복하는데, 이를 만들어놓고 끝까지 계속 돌려 쓰는 것이기 때문에 비교적 간단하게 코드를 구현할 수 있다.

단점: 깊이가 엄청 깊어지면, 메모리 비용을 예측하기 어렵다. 그리고 최단 경로를 알 수 없다.

-> 앞서 설명한 것처럼 깊이가 깊어질수록 함수가 하나씩 쌓이는 구조이다. 이 때문에 깊이가 엄청 깊어진다면 스택 메모리가 지나치게 커질 수 있다.

 

JavaScript에서 DFS의 원리

1. 큐에 시작 정점을 넣는다.
2. 큐에서 가장 오래있던 것을 뽑아낸다.(shift) 그와 관련된 것을 큐에 넣는다. 이때 뒤에 넣는게 아니라 앞에 넣는다.
3. 큐의 앞에 있는 정점을 뽑아내면서 또 위와 같은 과정으로 반복한다.
4. 큐가 빌때까지 계속 반복한다.

처음엔 1번으로 시작, 1번에서 갈 수 있는 곳이 어디지? 2,5,9번이 있네! 이걸 큐에 넣어놓자. 큐: 2 5 9
큐에 가장 먼저 있는게 뭐지?? 2번이네 2번 뽑아내고 연결된 정점이 뭐지? 3번이네 3번을 큐에 넣자. 큐: 3 5 9
또 큐에 뭐가 먼저 있지? 3번이네 3번과 연결된 정점은 뭐지? 4번이네. 이를 큐에 넣자 큐: 4 5 9
이 과정을 큐가 비어질 때까지 반복

 

그래프 생성

아래 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']
};

 

DFS 구현 함수

// graph 자료구조와 startNode를 입력
const DFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...graph[node], ...needVisit];
    }
  }
  return visited;
};

 

참고블로그: https://velog.io/@sean2337/Algorithm-DFS%EC%99%80-BFS%EC%9D%98-%EC%89%AC%EC%9A%B4-%EA%B0%9C%EB%85%90-JavaScript-%EA%B5%AC%ED%98%84-%EB%B0%A9%EB%B2%95