알고리즘 그래프와 탐색

준·2023년 10월 3일

BFS DFS 개발 공부 그래프 알고리즘 탐색

서두

프로젝트가 끝나면서 알고리즘을 다시하게 되었다.
시간상으로는 5개월만이다.
알고리즘을 처음에 공부할 때는 왜 알고리즘을 공부해야하는지 고민하였는데,
시간이 지나면서 나만의 답을 찾았다.

알고리즘은 컴퓨터에서 사용하는 자료구조에 대한 이해와 그것을 실제로 코드로 적용해보는 과정이고, 거기에 더해 사고를 확장하는 것이 목적이라는 생각에 도달하였다.
더 생각해보고 고민중이지만, 현재는 이렇다.

오늘은 인프런 강의를 이어서 다시 보았는데, 9강인 그래프에 대해 공부하였다.

1. 그래프

그래프(Graph)란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.

그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다.

G = (V, E)

수학적으로 그래프를 표시하는 방법이다.

V(G)는 그래프 G의 정점들의 집합텍스트을, E(G)는 그래프 G의 간선들의 집합을 의미한다.

그래프는 수학자 오일러(Euler)에 의해 창안되어 수학의 한 분야로서 수백 년 간 연구되어 왔지만, 컴퓨터 과학 분야에서 그래프 알고리즘을 다루기 시작한 것은 오래되지 않았다.

지하철 노선도, 도심의 도로 등 실생활의 다양한 예를 그래프로 표현하고 활용할 수 있으며, 특히 알고리즘에서 굉장히 많이 사용되므로 그래프에 대해 반드시 공부해야 한다.

※ 오일러 경로 (Eulerian Tour)
그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점으로 되돌아오는 경로
그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재 (오일러의 정리)

2. 그래프 용어

정점 (vertex) :

노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.

간선 (edge) :

링크(link)라고도 하며 정점 간의 관계를 나타낸다.

인접 정점 (adjacent vertex) :

하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻한다.
위 그래프에서 정점 C의 인접 정점은 A, D 이다.

차수(degree) :

정점에 연결된 간선의 수를 말한다.
위 그래프에서 정점 A의 차수는 3이고, 모든 정점의 차수를 합하면 8이다.
무방향 그래프에서 하나의 간선은 두 개의 정점에 인접하기 때문에 간선 수에 2배를 해주면 된다.

방향 그래프의 경우 외부에서 오는 간선의 수를 진입 차수(in-degree)라고 하며, 외부로 향하는 간선의 수를 진출 차수(out-degree)라고 한다.

경로 (path) :

간선을 따라갈 수 있는 길을 말하며, 정점을 나열하여 표시한다.
정점 s로부터 정점 e까지의 경로는 s, v₁, v₂ ... e로 표현하며, 반드시 정점들 간의 간선이 존재해야 한다.
너무나도 당연하게도 간선이 존재하지 않는 길은 경로가 될 수 없다.

경로의 길이 (length) :

경로를 구성하는 데 사용된 간선의 수를 뜻한다.

단순 경로 (simple path) :

경로 중에서 반복되는 간선이 없는 경로이다.

사이클 (cycle) :

시작 정점과 종료 정점이 같은 단순 경로를 뜻한다.
위 그래프에서 A, C, D, A 경로를 사이클이라고 한다.

추가로 그래프를 표현하는 방법에 대해서도 알아보자.

V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
V(G2) = {0, 1, 2, 3}, E(G2) = {(0, 1), (0, 2)}
V(G3) = (0, 1, 3}, E(G3) = {<0, 1>, <1, 0>, <1, 2>}

3. 그래프의 종류

그래프는 간선(edge)의 종류에 따라 구분된다.

무방향 그래프 (Undirected Graph)

두 정점을 연결하는 간선에 방향이 없는 그래프이며, 양 방향으로 이동이 가능하다.

위 그래프의 경우 (A, B)로 표현한다.

방향 그래프 (Directed Graph)

두 정점을 연결하는 간선에 방향이 존재하는 그래프이며, 간선의 방향으로만 이동할 수 있다.

위 그래프의 경우 <A, B>로 표현한다.

가중치 그래프 (Weighted Graph)

간선에 비용(cost) 또는 가중치(weight)가 할당된 그래프이다. 네트워크(network)라고 불리기도 한다.

완전 그래프 (Complete Graph)

모든 정점 간에 간선이 존재하는 그래프이다.

무방향 완전 그래프의 정점의 수가 n이라면, 전체 간선의 수는 n * (n-1) / 2 가 된다.

위 그래프의 경우 n=4이며 간선의 수는 (4*3)/2=6 이다.

1.5 그래프 구현 - 인접 행렬 (Adjacency Materix)
컴퓨터에서 그래프를 구현하는 방법에는 배열(Array)을 사용하는 방법과 연결리스트(Linked List)를 사용하는 방법이 있다.

4. 그래프 구현

컴퓨터에서 그래프를 구현하는 방법에는 배열(Array)을 사용하는 방법과 연결리스트(Linked List)를 사용하는 방법이 있다.

인접 행렬을 이용한 그래프 구현

그래프의 정점을 2차원 배열로 만든 것이다.

정점의 개수가 n이라면 n*n 형태의 2차원 배열이 인접 행렬로 사용된다.

인접 행렬에서 행과 열은 정점을 의미하며, 각각의 원소들은 정점 간의 간선을 나타낸다.

무방향 그래프는 (a), (b)에서 볼 수 있듯이 인접 행렬이 대칭적 구조를 가진다.
(두 개의 정점에서 간선이 동시에 연결되어 있기 때문)

가중치 그래프의 경우 행렬에서 0과 1이 아니라 각 간선의 가중치 값이 저장된다.
(이 경우 가중치가 0인 것과 간선이 없는 것이 구별돼야 함)

장점

2차원 배열에 모든 정점들의 간선 정보가 있기 때문에, 두 정점을 연결하는 간선을 조회할 때 O(1) 시간복잡도로 가능하다.

정점(i)의 차수를 구할 때는 다음과 같이 인접행렬(M)의 i번째 행의 값을 모두 더하면 되므로 O(n)의 시간복잡도를 가진다.

구현이 비교적 간단하다.

단점

간선의 수와 무관하게 항상 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n²)의 시간이 소요된다.

인접 리스트를 이용한 그래프 구현

그래프의 각 정점에 인접한 정점들을 연결리스트(Linked List)로 표현하는 방법이다.

즉 정점의 개수만큼 인접리스트가 존재하며, 각각의 인접리스트에는 인접한 정점 정보가 저장되는 것이다.

그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.

무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접리스트에 반대편 정점의 노드를 추가해야 한다.

장점

존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다.
그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더 노드부터 모든 인접리스트를 탐색해야 하므로 O(n+e)의 시간이 소요된다.

단점

두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요하다. O(degree(v))
구현이 비교적 어렵다.

인접 행렬 vs 인접 리스트

시간 복잡도를 얘기할 때 degree(v)는 그래프에서 특정 정점(vertex) v와 연결된 간선(edge)의 수를 의미합니다.

5. 탐색 방법

깊이우선탐색 (Depth First Search)

한 노드의 자식을 끝까지 순회한 후 다른 노드 순회
자식 우선
스택(LIFO) 사용

너비우선탐색 (Breadth First Search)

한 단계씩 내려가면서 같은 레벨에 있는 노드들을 먼저 순회
형제 우선
큐(FIFO) 사용

코드 구현

섬나라 아일랜드라는 문제를 기반으로 작성한 코드이다.

function solution(board) {
  let answer = 0;
  let n = board.length;
  let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
  let dy = [0, 1, 1, 1, 0, -1, -1, -1];

  function DFS(x, y) {
    board[x][y] = 0;
    for (let k = 0; k < 8; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];

      if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) {
        DFS(nx, ny);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let k = 0; k < n; k++) {
      if (board[i][k] === 1) {
        answer++;
        DFS(i, k);
      }
    }
  }
  return answer;
}

let arr = [
  [1, 1, 0, 0, 0, 1, 0],
  [0, 1, 1, 0, 1, 1, 0],
  [0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 1, 1],
  [1, 1, 0, 1, 1, 0, 0],
  [1, 0, 0, 0, 1, 0, 0],
  [1, 0, 1, 0, 1, 0, 0]
];

console.log(solution(arr));

function solution(board) {
  let answer = 0;
  let n = board.length;
  let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
  let dy = [0, 1, 1, 1, 0, -1, -1, -1];
  let queue = [];
  for (let i = 0; i < n; i++) {
    for (let k = 0; k < n; k++) {
      if (board[i][k] === 1) {
        answer += 1;
        board[i][k] = 0;

        queue.push([i, k]);
        while (queue.length) {
          let [x, y] = queue.shift();
          for (let j = 0; j < 8; j++) {
            let nx = dx[j] + x;
            let ny = dy[j] + y;
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) {
              board[nx][ny] = 0;
              queue.push([nx, ny]);
            }
          }
        }
      }
    }
  }
  return answer;
}

let arr = [
  [1, 1, 0, 0, 0, 1, 0],
  [0, 1, 1, 0, 1, 1, 0],
  [0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 1, 1],
  [1, 1, 0, 1, 1, 0, 0],
  [1, 0, 0, 0, 1, 0, 0],
  [1, 0, 1, 0, 1, 0, 0]
];

console.log(solution(arr));