알고리즘 준비하기 - 그래프와 DFS

🎯 그래프(Graph)

그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조로 실제 세계의 현상이나 사물을 정점(V)과 간선(E)으로 표현한 것이다. 한마디로 그래프는 정점과 간선들의 유한집합이라고 통칭할 수 있다.

💎 그래프의 표현 방법

프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데 인접 행렬과 인접 리스트이다.

인접 행렬은 2차원 배열로 각 노드의 연결 관계를 표현하는 방식이다. 연결이 되어 있지 않은 노트끼리 무한의 비용이라고 작성한다. 노드에 대해 가중치가 있을 때는 가중치를 입력해주고 가중치가 없는 경우에는 1과 0으로 표기한다. 인접 행렬 방식을 사용하면 노드의 연결 관계를 담은 배열이 중앙 대각선을 기준으로 대칭을 이루게 된다.

// 가중치가 없는 인접 행렬 그래프
const graph = [
  [0, 1, 0, 1, 1, 0],
  [1, 0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0, 0],
  [1, 0, 1, 0, 0, 0],
  [1, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 1, 0],
];

// 가중치가 있는 인접 행렬 그래프
const INF = Number.MAX_SAFE_INTEGER;

const weighted_graph = [
  [0, 9, INF, 2, 7, INF],
  [9, 0, 20, INF, INF, INF],
  [INF, 20, 0, 16, INF, INF],
  [2, INF, 16, 0, INF, INF],
  [7, INF, INF, INF, 0, 10],
  [INF, INF, INF, INF, 10, 0],
];

반면 인접 리스트는 리스트로 그래프의 연결 관계를 표현하는 방식으로 모든 노드에 연결 정보를 차례대로 연결하여 저장한다. 노드에 대해 가중치가 있을 때는 아래와 같이 가중치를 입력해주고 가중치가 없는 경우에는 2차원 배열로 표기한다.

// 가중치가 없는 인접 리스트 그래프
// 해당 배열의 index와 연결된 노드를 적어준다
const graph = [[1, 3, 4], [0, 2], [1, 3], [0, 2], [0, 5], [4]];

// 가중치가 있는 인접 리스트 그래프
const weighted_graph = [
  [
    [1, 9],
    [3, 2],
    [4, 7],
  ],
  [
    [0, 9],
    [2, 20],
  ],
  [
    [1, 20],
    [3, 16],
  ],
  [
    [0, 2],
    [2, 16],
  ],
  [
    [0, 7],
    [5, 10],
  ],
  [[4, 10]],
];

💎 인접 행렬과 인접 리스트 방식의 차이점

메모리 측면에서 보자면 인접 행렬 방식은 노드의 모든 관계를 저장하므로 메모리를 불필요하게 많이 사용하게 된다. 반면 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용하게 된다. 하지만 인접 리스트 방식은 연결된 데이터를 하나씩 확인해야 하므로 인접 행렬 방식에 비해 특정한 두 노드의 연결에 대한 정보를 얻는 속도가 느리다.

우선 메모리를 많이 소모하는 프로그램을 작성하는 경우에는 인접 행렬 방식이 더 유리하지만 조금 복잡한 로직을 짜야하는 문제라면 리스트로 접근하는 방식이 낫다.

🎯 DFS

DFS(Depth-First-Search)는 깊이 우선 탐색이라고 하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 트리에서 생각하면 이해하기 쉽고, 사실 트리도 그래프의 부분이다. 트리를 탐색할 때 시작 노드에서 한 방향으로 계속 탐색하다가 더 이상 갈 수 없을 때 다시 가장 가까운 노드로 되돌아와 다시 탐색을 진행하는 방법으로 생각하면 된다.

DFS를 구현하는 데는 2가지의 방법이 있다. 하나는 재귀를 이용하는 것이고 다른 하나는 스택을 이용하는 것이다.

💎 재귀를 이용한 DFS 구현 (JS)

우선 한번 방문했던 노드는 방문하지 않을 예정이기 때문에 방문 여부를 기록하는 visited라는 배열을 사용하며 초기값은 전부 false로 한다.

노드를 방문할 때마다 해당 노드의 visited 배열 값을 true로 변경한다.

해당 노드와 연결된 노드 중에서 방문하지 않은 노드가 있다면 방문하지 않은 노드를 시작점으로 하여 DFS를 다시 시작한다.

function dfs(graph, v, visited) {
  // 현재 노드를 방문 처리
  visited[v] = true;
  console.log(v);

  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for (let node of graph[v]) {
    if (!visited[node]) {
      dfs(graph, node, visited);
    }
  }
}

const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);

위의 코드에서 그래프는 인접 리스트로 구현해놓은 상태이다. 이것과 매우 유사한 문제가 바로 백준 실버3 바이러스 문제이다. 여기서 똑같은 오류가 발생하여 이해하는데 반나절 이상 걸렸는데 코드를 같이 보며 이해해보자.

const array = input.map((value) => value.split(' ').map(Number));
const graph = [...new Array(N + 1)].map(() => []);
const visited = Array(graph.length).fill(false);

for (let i = 0; i < array.length; i += 1) {
  graph[array[i][0]].push(array[i][1]);
  graph[array[i][1]].push(array[i][0]);
}

DFS 구현은 바로 전 코드를 확인하면 되는데 초기 그래프를 세팅하는 것이 상당히 헷갈린다. 인접 리스트 구현 부분에서 주석에도 적어놓았지만 해당 노드에 해당되는 index값을 가진 배열에 인접 노드를 적는 것을 따로 구현해줘야 한다.

💎 스택을 이용한 DFS 구현 (JS)

사실 이 부분이 메인이다. 재귀를 이용하여 구현하는 방법이 코드도 직관적이라 이해하기 편한데 자바스크립트에서는 재귀를 사용하면 CallStack이 터져버리는 경우가 종종 발생한다고 한다. 따라서 스택으로 문제를 해결하는 것에 초점을 맞춰나가야할 것 같다… 내 자의는 아니다.

우선 스택에 노드를 push한다. 스택에서 노드를 pop하고 해당 노드가 방문하지 않은 노드라면 방문 처리를 한다. 노드와 연결된 노드 중에서 방문하지 않은 노드가 있다면 stack에 push한다. 스택의 길이가 0이 될 때까지 이 과정을 반복한다.

function dfs(graph, start, visited) {
  const stack = [];
  stack.push(start);

  while (stack.length) {
    let v = stack.pop();
    if (!visited[v]) {
      console.log(v);
      visited[v] = true;

      for (let node of graph[v]) {
        if (!visited[node]) {
          stack.push(node);
        }
      }
    }
  }
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);

하지만 위 코드의 가장 치명적인 단점이 있다. 바로 재귀로 호출한 DFS와는 다르게 부모 노드를 알 수 있는 방법이 없다. 스택의 상단에 있는 노드를 계속 탐색하기 때문에 현재 노드의 부모 노드로 돌아가는 로직이 없다. 따라서 스택 DFS가 재귀 DFS와 같이 동작하도록 하려면 부모 노드로 돌아가는 로직을 추가해줘야 한다.

function dfs(graph, visited) {
  const stack = [[0, -1]];

  while (stack.length) {
    let [cur, parent] = stack.pop();

    if (visited[cur]) {
      // 이 부분이 기존의 Iterative DFS에서 빠져 있던 부분이고
      // Recursive DFS와 같게 만들어 주는데 필요한 로직이다.
      continue;
    }

    stack.push([cur, parent]);
    visited[cur] = true;

    console.log(cur);

    // 방문하지 않았던 노드라면 `cur`은 부모 노드가 되어 다음 노드를 계속 탐색하게 된다.
    for (const node of graph[cur]) {
      if (!visited[node]) stack.push([node, cur]);
    }
  }
}

위 코드와 같이 현재의 노드와 부모 노드를 하나의 배열로 담아준다. 루트 노드의 경우는 부모 노드가 없으므로 -1, null, undefined 등 존재할 수 없는 수를 넣어준다. 이후에 부모 노드를 추적하고 부모 노드로 되돌아가는 로직을 수행하기 위해 스택에서 pop하고 다시 push해주는 작업을 하게 된다. push와 pop 사이에서 무한루프에 빠지지 않도록 방문했다면 continue문을 통해 다시 다음 과정을 수행하게 된다.

🎯 DFS의 시간 복잡도

노드의 수가 N이고 간선의 수가 E인 그래프에서 그래프가 인접 리스트로 표현되어 있다면 O(N+E)이고, 인접 행렬로 표시되어 있다면 O(N^2)이다. 이는 인접 리스트의 사용이 인접 행렬보다 시간적으로 유리함을 의미한다.

Reference

chamdom Blog