알고리즘 | 깊이 우선 탐색 DFS 알고리즘 - 그래프 탐색

dev_hee·2021년 10월 8일

DFS JavaScript 그래프 알고리즘 자바스크립트

알고리즘

목록 보기

3/7

깊이 우선 탐색(DFS)으로 그래프를 탐색해보자.

그래프 탐색

하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다.

특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다.

깊이 우선 탐색 DFS

DFS는 탐색에서 깊은 것을 우선적으로 탐색하는 알고리즘이다.

너비 우선 탐색 (BFS)는 큐(queue)가 사용되지만, 깊이 우선 탐색 (DFS)는 스택(stack)이 사용된다.

사실 컴퓨터는 함수 호출을 스택의 원리를 사용하기 때문에, 재귀를 사용하면 DFS를 구현할 수 있다.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 모든 경우의 수를 보기 좋다!
BFS보다는 속도가 느리다.
어떤 노드를 방문했는지 검사하여야한다.

DFS의 동작 방식

방문하지 않은 인접한 노드가 있는 경우 방문하고, 방문 처리한다.
만약 더이상 방문하지 않은 인접 노드가 없다면(모두 방문했다면), 순회를 종료한다.

그래프 탐색 예제

백준 1260 https://www.acmicpc.net/problem/1260

아래와 같은 그래프가 있을 때, DFS로 방문해 보자.

정점은 1~4번 노드가 존재한다.
간선은 서로 다음과 같이 연결되어 있다.

노드	연결된 노드
1	2, 3, 4
2	1, 4
3	1, 4
4	1, 2, 3

출발 노드는 1번 노드이다.

다음은 그래프의 방문 순서를 표현한 것이다.

노란색은 현재 탐색하는 노드, 회색은 이미 방문한 노드, 하얀색은 방문하지 않은 노드다.

(1) 현재 탐색 노드 == 1

노드 1을 탐색하였으므로 방문 처리한다.

연결된 2, 3, 4는 전부 방문 하지 않았다. 그 중에서 먼저 2번 부터 탐색할 것이다. (2)로 진행한다.

(2) 현재 탐색 노드 == 2

노드 2를 탐색하였으므로 방문 처리한다.

2와 연결된 1과 4번 노드중, 1번 노드는 이미 방문했으므로 탐색하지 않고, 4번을 탐색할 것이다. (3)으로 진행한다.

(3) 현재 탐색 노드 == 4

노드 4를 탐색하였으므로 방문 처리한다.

4와 연결된 1, 2, 3번 노드중, 1, 2번 노드는 이미 방문했으므로 탐색하지 않고, 3번을 탐색할 것이다. (4)로 진행한다.

(4) 현재 탐색 노드 == 3

노드 3을 탐색하였으므로 방문 처리한다.

3과 연결된 1, 4노드 모두 방문했으므로 탐색을 종료한다.

위와 같은 알고리즘을 자바스크립트 코드로 작성하면 다음과 같다.

function DFS을 참고하면 된다.

function solution(n, m, v, road) {
    let graph = Array.from(Array(n + 1), () => Array());
    let ch = Array(n + 1).fill(0);
    let answer = [];

    // 연결된 노드 표시하기
    for (let i = 0; i < m; i++) {
      graph[road[i][0]].push(road[i][1]);
      graph[road[i][1]].push(road[i][0]);
    }
    // 연결된 노드를 오름차순으로 정렬하기
    for (let i = 1; i <= n; i++) {
      graph[i].sort((a, b) => a - b);
    }

    function DFS(L) {
      // 방문한 노드면 탈출
      if (ch[L] === 1) return;
      else {
        // 방문하지 않았다면 인접한 노드 방문하기
        ch[L] = 1;
        answer.push(L);
        for (let node of graph[L]) {
          DFS(node);
        }
      }
    }

    DFS(v);
    return answer;
  }
  console.log(
    solution(4, 5, 1, [
      [1, 2],
      [1, 3],
      [1, 4],
      [2, 4],
      [3, 4],
    ])
  ); // [ 1, 2, 4, 3 ]
  console.log(
    solution(5, 5, 3, [
      [5, 4],
      [5, 2],
      [1, 2],
      [3, 4],
      [3, 1],
    ])
  ); // [ 3, 1, 2, 5, 4 ]
  console.log(
    solution(1000, 1, 1000, [
      [999, 1000],
      [999, 1000],
    ])
  ); // [ 1000, 999 ]