sungyup's.

javascript_algorithm / 데이터 구조 / 4.10 Graph Traversal

4.10Graph Traversal

그래프 데이터를 탐색하는 두 가지 방법(DFS, BFS) 구현하기

Graph Traversal

지난번 포스팅에서 살펴봤듯이, 그래프는 SNS 네트워킹, 길 찾기, 추천 시스템 등에 빈번하게 쓰이는 데이터 구조다. 예를 들어, 아래와 같은 데이터 구조가 있다면 Tim이 누구를 '알 수도 있는지' 데이터를 근거로 하여 정량적 수치로 파악할 수 있다.

graph traversal
이미지 출처 : #
Tim에게 추천할 만한 사람을 찾기에 그래프 구조는 아주 유용하다. 다만, 어떻게 그래프를 탐색할 것인가?

Tree Traversal과 마찬가지로, 그래프 탐색 또한 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(Breadth-First Search)이 있다.

깊이 우선 탐색

트리와 달리, 그래프는 루트 노드가 없다. 깊이 우선 탐색이 루트 노드로부터 먼 노드부터 탐색하는 방법이라는 사실을 생각해보면, 그래프에서의 깊이 우선 탐색은 어떨까?

그래프에서도 탐색은 기준이 되는 노드가 있어야 한다. 이 노드는 탐색을 시작하는 노드로, 앞서 Tim에게 친구를 추천해주는 그래프 탐색이라면 Tim이 기준 노드고, 현재 위치에서 특정 위치로 가는 길을 찾는 그래프 탐색이라면 현재 위치가 기준 노드다.

따라서 그래프에서의 깊이 우선 탐색은 기준이 되는 노드로부터 이웃이 되는 노드로 가고, 그 노드의 이웃이 되는 노드로 가고... 하는 방식으로 탐색을 하는 방식이다.

다만, 트리와 달리 그래프에선 부모-자식 관계가 없기 때문에 한번 거쳤던 정점을 기억하고 있어야만 한다. 예를 들어, 아래의 그래프에서 A부터 시작해 깊이 우선 탐색을 한다고 해보자.

graph_dfs
이미지 출처 : #

A에서 시작해 B로 간다면, 고민없이 D로 가면 될 것 같지만, 만약 A를 이미 거쳤다는 정보가 없다면 B 정점(vertex)는 A와 D를 이웃하고 있다는 정보를 가지고 있을 것이므로 A 또는 D로 이동할 수 있다.

그래프에서 깊이 우선 탐색은 재귀적으로 하는 방법과 반복적으로 하는 방법 두 가지가 있다.

1. DFS 구현하기-재귀

재귀적으로 DFS를 구현하는 수도코드를 작성한다면 아래와 같을 것이다:

  • 시작 정점을 받아 깊이 우선 탐색을 수행하는 함수를 선언한다.
  • 최종 탐색 결과를 반환할 배열과, 이미 방문한 데이터를 저장해둘 객체를 만든다.
  • 재귀적으로 실행할 헬퍼 함수를 선언한다.
    • 만약 시작 정점이 고립되어 있다면(빈 배열이라면) 그냥 반환한다.
    • 시작 정점이 연결이 있다면, 해당 정점은 방문한 것으로 데이터를 저장해두고 최종 탐색 결과를 반환할 배열에 추가해둔다. 예를 들어, {"A": true}식이다.
    • 해당 정점의 각 이웃들에 대해서, 방문 전이라면 DFS 함수를 재귀적으로 호출한다.
  • 결과 배열을 반환한다.

이번 포스팅에선 이전 포스팅에서 작성한 그래프 클래스에 메소드를 추가한다.

javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  depthFirstRecursive(start){
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList; // 아래 dfs 헬퍼 함수에서 this의 컨텍스트가 바뀌기 때문에 변수로 저장해서 쓰기 위함

    (function dfs(vertex){
      if(!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
        if(!visited[neighbor]){
          return dfs(neighbor);
        }
      })
    })(start);

    return result;
  }
}

2. DFS 구현하기-반복

반복문으로 DFS를 구현해보자. 수도코드를 작성한다면 아래와 같을 것이다:

  • 시작 정점을 받아 깊이 우선 탐색을 수행하는 함수를 선언한다.
  • 탐색 과정을 기록할 스택(여기선 배열을 활용하자)을 만든다.
    • 깊이를 우선적으로 탐색할 것이기 때문에, 먼저 방문한 정점은 그 이웃에 이웃에 이웃의...를 방문하기 전까지는 남아 있어야 한다.
  • 최종 탐색 결과를 반환할 배열과, 이미 방문한 데이터를 저장해둘 객체를 만든다.
  • 시작 정점을 스택에 넣고, 방문한 데이터에 저장한다.
  • 스택에 뭔가가 있는 동안 아래를 반복한다:
    • 스택의 데이터를 pop한다.
    • 해당 정점이 아직 방문이 되지 않았다면, 방문한 것으로 표시하고, 결과 배열에 추가한다. 해당 정점과 이웃한 모든 정점을 스택에 넣는다.
  • 결과 배열을 반환한다.
javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  depthFirstIterative(start){
    const stack = [start];
    const result = [];
    const visited = {};
    let currentVertex; // 루프 안에서 선언하면 계속 재선언하게 되므로 밖에서 선언

    visited[start] = true;
    while(stack.length){
      currentVertex = stack.pop();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach(neighbor => {
        if(!visited[neighbor]){
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      })
    }

    return result;
  }
}

너비 우선 탐색

깊이 우선 탐색과 달리, 너비 우선 탐색은 우선 시작 정점과 인접한 정점들을 먼저 모두 탐색하는 탐색 방법이다.

  • 시작 정점을 받아 너비 우선 탐색을 수행하는 함수를 선언한다.
  • 큐를 만들고(여기서 우리는 배열을 활용한다), 시작 정점을 추가한다.
  • 최종 탐색 결과를 반환할 배열과, 이미 방문한 데이터를 저장해둘 객체를 만든다.
  • 시작 정점을 방문한 것으로 추가한다.
  • 큐에 뭔가가 있는한 아래의 루프를 반복한다:
    • 큐의 첫번째 정점을 제거하고, 방문한 데이터를 저장하는 객체에 추가한다.
    • 해당 정점의 인접한 정점들을 순회한다.
    • 순회 중 방문한 정점이 방문한 데이터를 저장한 객체에 없다면, 해당 정점을 추가하고 큐에 추가한다.
  • 최종 탐색 결과를 반환한다.
javascript
class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  breadthFirst(start){
    const queue = [start];
    const result = [];
    const visited = {};
    let currentVertex; // 루프 안에서 선언하면 계속 재선언하게 되므로 밖에서 선언

    visited[start] = true;
    while(queue.length){
      currentVertex = queue.shift();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach(neighbor => {
        if(!visited[neighbor]){
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      })
    }
    return result;
  }
}

🤠 개인 탐구

프로그래머스는 코딩테스트 고득점 Kit 카테고리에 그래프 문제 3문제를 제공한다. 이 문제들을 풀어보면서 복습하고자 한다.

1. 가장 먼 노드(Lv.3)

가장 먼 노드는 n개의 노드가 있는 그래프에서, 간선(edge)에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 반환하는 함수를 작성하는 문제다. 여기서, 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드다.

다른 노드들까지의 "최단 거리"를 찾는 것이므로 BFS 문제다. BFS는 층층이 퍼지듯이 탐색하기 때문에 최단 거리를 보장하지만, DFS는 경로는 찾지만 먼저 깊이 들어가는 방식이라 최단 경로를 보장하지 못하고, 더 긴 경로를 먼저 탐색할 수도 있기 때문이다.

양방향 그래프 인접 목록을 생성하고, BFS로 1번 노드에서 다른 노드로의 최단 거리를 구한다. 이후, 가장 먼 거리의 값을 찾고 그 거리를 가진 노드의 개수를 반환한다.

javascript
function solution(n, edge) {
    const graph = Array.from({length: n + 1}, () => []);
    const visited = Array(n + 1).fill(false);
    const distance = Array(n + 1).fill(0);
    
    for(const [a, b] of edge){
        graph[a].push(b);
        graph[b].push(a);
    }
    
    const queue = [1];
    visited[1] = true;
    
    while(queue.length){
        const current = queue.shift();
        
        for(const next of graph[current]){
            if(!visited[next]){
                visited[next] = true;
                distance[next] = distance[current] + 1;
                queue.push(next);
            }
        }
    }
    const maxDistance = Math.max(...distance);
    return distance.filter(d => d === maxDistance).length;
}

2. 순위(Lv.3)

순위는 권투 선수의 수 n과 경기 결과를 담은 2차원 배열 results가 매개 변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 반환하는 함수를 작성하는 문제다. 경기 결과에는 모순이 없기 때문에, 예를 들어 5명이 주어졌을 때 한 선수가 4위인 선수에게 패했으면 그 선수는 다른 모든 선수에게도 패하는 5위 선수이다.

그래프의 용어로 번역하면, 이 문제는 각 선수 간의 승패 기록으로 누가 누구를 이겼는지, 즉 방향이 있는 유향 그래프를 만들고 이를 기반으로 이긴 사람/진 사람을 전부 알아낼 수 있는 사람이 있다면 순위를 정확히 판단할 수 있는 사람이다. 순위를 정확히 판단할 수 있으려면 이긴 사람 + 진 사람의 총합이 n - 1인 사람이 있다면 그 사람은 순위를 확정할 수 있는 사람이다.

확인을 위해 각 선수(노드)에 대해 그 선수가 이긴 사람들과 그 선수에게 이긴 사람들을 DFS로 탐색하고, 수를 합산해서 n - 1인지 확인한다.

javascript
function solution(n, results) {
    const winGraph = Array.from({ length: n + 1 }, () => []);
    const loseGraph = Array.from({ length: n + 1 }, () => []);

    for (const [winner, loser] of results) {
        winGraph[winner].push(loser); // winner -> loser
        loseGraph[loser].push(winner); // loser <- winner
    }

    function dfs(start, graph, visited) {
        for (const next of graph[start]) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next, graph, visited);
            }
        }
    }

    let count = 0;
    for (let i = 1; i <= n; i++) {
        const visitedWin = Array(n + 1).fill(false);
        const visitedLose = Array(n + 1).fill(false);
        dfs(i, winGraph, visitedWin);  // 해당 선수가 이긴 사람
        dfs(i, loseGraph, visitedLose); // 해당 선수를 이긴 사람

        const known = visitedWin.filter(v => v).length + visitedLose.filter(v => v).length;
        if (known === n - 1) count++;
    }

    return count;
}

이 문제는 BFS로도 풀 수 있다. dfs 함수 대신 bfs를 만들어 쓰면 된다.

javascript
function solution(n, results) {
    const winGraph = Array.from({ length: n + 1 }, () => []);
    const loseGraph = Array.from({ length: n + 1 }, () => []);

    for (const [winner, loser] of results) {
        winGraph[winner].push(loser);
        loseGraph[loser].push(winner);
    }

    function bfs(start, graph) {
        const visited = Array(n + 1).fill(false);
        const queue = [start];
        visited[start] = true;
        let count = 0;

        while (queue.length > 0) {
            const current = queue.shift();
            for (const next of graph[current]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.push(next);
                    count++;
                }
            }
        }

        return count;
    }

    let answer = 0;
    for (let i = 1; i <= n; i++) {
        const winCount = bfs(i, winGraph);  // 해당 선수가 이긴 사람 수
        const loseCount = bfs(i, loseGraph); // 해당 선수가 진 사람 수
        if (winCount + loseCount === n - 1) answer++;
    }

    return answer;
}

DFS, BFS 외에도 이 문제는 플로이드 와샬 방식(Floyd-Warshall)이라는 방법으로도 풀 수 있다. 이 방법은 모든 선수 간의 승패를 기록하는데, graph[i][j]는 i가 j를 이겼으면 true를 저장한다. 또, i가 j를 이겼고 j가 k를 이겼으면 i는 k를 이겼다는 것을 전제로 한다.

javascript
function solution(n, results) {
    const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(false));

    for (const [a, b] of results) {
        graph[a][b] = true;
    }

    // 플로이드 와샬
    for (let k = 1; k <= n; k++) {
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= n; j++) {
                if (graph[i][k] && graph[k][j]) {
                    graph[i][j] = true;
                }
            }
        }
    }

    let answer = 0;
    for (let i = 1; i <= n; i++) {
        let count = 0;
        for (let j = 1; j <= n; j++) {
            if (i === j) continue;
            if (graph[i][j] || graph[j][i]) count++;
        }
        if (count === n - 1) answer++;
    }

    return answer;
}

DFS와 BFS는 O(n ^ 2)의 시간복잡도를 가지는데 비해 플로이드 와샬은 3중 for문으로 시간복잡도가 O(n ^ 3)이다. 이는 모든 경로를 탐색하기 때문이며, 시간 복잡도가 아주 높지만 작은 n일때는 안정적이다.

3. 네트워크(Lv.3)

네트워크는 DFS/BFS 카테고리에 있는 그래프 문제로, 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 주어지면 네트워크의 개수(서로 연결되지 않고 별도로 존재하는 네트워크 수)를 구하라는 문제다.

여기서 주어진 computers는 인접 행렬(Adjacency Matrix)다. 이 문제는 DFS 또는 BFS로 풀 수 있다.

3-1. 네트워크(DFS)

javascript
function solution(n, computers){
  const visited = new Array(n).fill(false);
  let count = 0;

  function dfs(node){
    visited[node] = true;

    for(let i = 0; i < n; i++){
      if(!visited[i] && computers[node][i] === 1){
        dfs(i);
      }
    }
  }

  for(let i = 0; i < n; i++){
    if(!visited[i]){
      dfs(i);
      count++;
    }
  }
  return count;
}

3-2. 네트워크(BFS)

javascript
function solution(n, computers) {
    const visited = new Array(n).fill(false);
    let count = 0;

    function bfs(start) {
        const queue = [start];
        visited[start] = true;

        while (queue.length) {
            const node = queue.shift();

            for (let i = 0; i < n; i++) {
                if (computers[node][i] === 1 && !visited[i]) {
                    visited[i] = true;
                    queue.push(i);
                }
            }
        }
    }

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(i);
            count++;
        }
    }

    return count;
}
PreviousGraphs
Algorithm
NextDijkstra's Algorithm
Algorithm