그래프 탐색

그래프의 기본 개념과 탐색 방법

그래프 개념

정점과 간선

• 정점 (vertex)

  • 노드라고 불리며 그래프를 형성하는 기본 단위이다.

  • 분할할 수 없는 객체이자, 점으로 표현되는 점, 위치, 사람 등이 될 수 있다.

• 간선 (Edge)

  • 정점을 잇는 선으로, 관계 경로 등이 될 수 있다.

  • 간선에 방향에 따라 단방향간선, 양방향 간선으로 구분할 수 있다.

• 그래프 (Graph)

  • 정점과 간선의 집합

indegree와 outdegree

• indgree : 정점으로 들어오는 간선

• outdegree : 정점으로 나가는 간선

• 보통 정점은 약자로 V 또는 U라고 표시하며 U(From)로부터 V(To)로 간다고 표현한다.

가중치

• 노드에서 다른 노드까지의 비용으로, 간선 비용의 합이다.

트리

자식 노드와 부모 노드로 이루어진 계층으로, 무방향 그래프이며 사이클이 없다

특징

• 그래프(정점과 간선의 집합)의 일종이다.

• 부모, 자식 계층 구조를 가진다.

• V-1 = E라는 특징이 있다.

  • 정점 : Vertex

  • 간선 : Edge

  • 간선 수 = 노드 수 - 1

• 임의의 두 노드 사이의 경로는 유일무이하게 존재한다.

  • 즉, 트리 내 특정 노드까지의 경로는 반드시 존재하며, 하나만 존재한다.

• 루트, 내부, 리프노드로 구성된다.

트리의 높이와 레벨

• 트리의 높이

  • 루트노드부터 최하단 리프노드까지의 길이

• 서브트리

  • 트리 내에 있는 트리 (부분 집합)

• 깊이

  • 각 노드마다 다르며, 루트 노드에서 특정 노드까지 최단 거리로 갔을 때의 거리

• 레벨

  • 보통 깊이와 같은 의미를 지닌다.

  • 루트노드의 시작 레벨에 따라 상대적으로 결정된다.

    • 1번 노드가 0레벨이라면, 2번노드는 1

    • 1번 노드가 1레벨이라면, 2번노드는 2

• 숲

  • 트리로 이루어진 집합

이진트리와 이진탐색트리

이진트리 (BT, BinaryTree)

• 각 노드의 자식 노드 수가 2개 이하로 구성되어있는 트리이다.

  • 정이진 트리(full binary tree) : 자식노드가 0개 또는 2개

  • 완전 이진 트리 (complete binary tree) : 왼쪽부터 채워져있는 트리로, 마지막 레벨을 제외하고는 완전히 채워져있으며, 마지막 레벨은 왼쪽부터 채워진다.

  • 변질 이진 트리 (degenerate binary tree) : 자식 노드가 하나밖에 없는 이진 트리

  • 포화 이진 트리 (Perfect binary tree) : 모든 노드가 가득 차 있는 이진트리

  • 균형 이진 트리 (balanced binary tree) : 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 차이가 1 이하인 트리이다. Map, set을 구성하는 레드블랙트리는 균형 이진트리 중 하나이다.

이진 탐색 트리 (BST, Binary Search Tree)

• 이진 트리의 일종으로, 오른쪽 하위 트리에는 노드의 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위트리에는 노드의 값보다 작은 값이 들어있는 트리이다.

• 검색에 유리하다.

  • 10을 찾는 과정에서 25보다 10이 작으므로, 왼쪽 노드를 탐색한다.

    → 20보다 작으므로 왼쪽 노드로 탐색한다 → 10을 찾을 수 있다.

  • Up and down도 binary search tree에 들어간다.

• 이진탐색트리의 시간복잡도

  • 위 사진처럼 균형잡히게 분포되었다면 탐색, 삽입, 삭제, 수정 모두 O(logN)이다.

• 이진 탐색 트리의 모양은 노드 삽입 순서에 따라 달라진다. 1, 2, 3 순서로 삽입이 된다면 선형적 자료구조가 된다.

  • 이런 모양이 된다면, 탐색에 최악의 경우 O(logN)이 아닌 O(N)이 된다.

• 삽입 순서에 상관 없이 트리의 노드를 회전시키는 방법 등을 통해 균형 잡게 만드는 것을 AVL 트리, 레드블랙트리가 있다.

  • map 자료구조는, 삽입 탐색 삭제 수정의 시간복잡도가 O(logN)임을 보장받는데, 그 이유가 균형잡힌 트리인 레드블랙트리를 기반으로 구현되어있기 때문이다.

그래프 구현과 탐색

그래프를 컴퓨터가 이해할 수 있도록 코드로 작성해야한다.

인접행렬

• 정점과 간선의 관계를 나타내는 2차원 행렬

• true, false를 이용하여 연결되어있는지 표현한다.

인접리스트 (adjancency list)

• 연결리스트럴 여러개 만들어 표현하는 방법이다.

• 각 정점마다 연결리스트를 만들고, 연결된 정점을 저장한다.

인접행렬과 인접리스트의 차이

1. 공간복잡도

   • 인접행렬 : O(V^2)

   • 인접리스트 : O(V + E)

     • 연결된 정점만 데이터가 들어간다.

     • 정점이 여러개가 있더라도 연결된 정점만 들어가므로, 간선의 개수만 들어가게 되는것이다

2. (최악) 시간복잡도

   1. 간선 한 개 찾기

      • 노드 i에서 노드 j로 가는 간선이 있는가?

        • 인접행렬 = O(1)

        • 인접리스트 = O(V)

        // 인접행렬
        if a[i][j]
        
        // 인접리스트
        if adj.values.contains(j)

   2. 모든 간선 찾기

      • 인접행렬 : O(V^2)

      • 인접리스트 : O(V + E)

3. 그래서 언제 인접 리스트, 인접 행렬을 써야할까?

   • 그래프가 희소한 경우(sparse) 인접리스트, 조밀할 때(dense)에는 인접 행렬을 쓴다.

   • 연결된 정점이 많이 없을 때에는 인접 리스트를 쓰는 것이 더 빠르고 좋다.

     • 인접행렬의 경우 무식하게 이차원 배열을 만들게 된다.

     • 연결되지 않은 노드들을 위해서도 이차원 배열을 만들게 된다.

   • 그래프가 조밀할 때 (간선이 너무 많을 때) 인접 행렬이 더 좋다.

     • 어차피 노드들이 모두 연결되어있다면 메모리적 효율성이 동일하므로, 하나의 간선을 찾는데에 속도가 더 빠른 인접 행렬이 더 빠르다.

   • 보통 코딩테스트에는 희소한 그래프가 나오니 연결리스트로 사용하는게 좋지만, 인접행렬로 주어진다면 주어진대로 문제를 푸는 것이 좋다.

연결된 컴포넌트(Connected component)

• 그래프 안에 하위그래프를 말하며, 하나의 덩어리라고 볼 수 있다.

• 연결된 컴포넌트에 속한 모든 정점을 연결하는 경로가 있다는 특징이 있다.

• 컴포넌트들에 번호를 붙여가며 색칠하는 알고리즘을 풀르드필(floodfill)이라고 한다.

  • 첫번재 연결된 컴포넌트에서 연결된 모든 노드는 1번

  • 두 번째 연결된 컴포넌트에서 연결된 모든 노드는 2번 이런 식으로

  • 해당 번호는 연결된 덩어리의 개수만큼만 나온다.

• 만약 맵으로 주어지는 상황에서도 갈 수 있는 지점을 통해 정점의 집합을 만들 수 있다. 이를 기반으로 connected component로 만들어보자.

그래프 탐색 방법

깊이 우선 탐색 (DFS, Depth First Search)

• 그래프를 탐색할 때 쓰는 알고리즘이다.

• 인접한 노드들을 재귀적으로 방문하며, 방문한 정점은 다시 방문하지 않는다.

  • 각 분기마다 가장 멀리 있는 노드까지 탐색하는 알고리즘이다.

• 수도코드

  DFS(u, adj)
      u.visited = true
      for each v ∈ adj[u] // 인접 리스트를 조회. ∈: 포함
          if v.visited == false // 방문하지 않았다면
              DFS(v, adj) // 재귀함수

• DFS 코드

  var graph: [Int: [Int]] = [:]
  var visited = [Bool](repeating: false, count: 10)
  
  graph[1] = [2, 3]
  graph[2] = [4, 5]
  graph[3] = [1]
  graph[4] = [2]
  graph[5] = [2]
  dfs(u: 1) // 1 2 4 5 3
  
  func dfs(u: Int) {
      print(u)
      visited[u] = true
      for v in graph[u]! {
          if !visited[v] {
              dfs(u: v)
          }
      }
  }

func dfs(u: Int) {
    print(u)
    visited[u] = true
    for v in graph[u]! {
        **if !visited[v] {**
            **dfs(u: v)
        }**
    }
}

너비 우선 탐색 (BFS, Breadth First Search)

• 다음 깊이의 정점으로 이동하기 전, 현재 깊이의 모든 정점을 탐색하며, 방문한 정점은 다시 방문하지 않는 알고리즘이다.

  • 같은 가중치를 가진 그래프에서 최단 거리 알고리즘으로 쓰인다.

  • Layer별, Level 별로 탐색한다는 의미이다.

• BFS 구현 방법

  • 자료구조 큐(Queue)를 사용하면 레벨 별로 탐색이 가능하다.

    // Queue 구현(참고, 구현하지 않아도 된다.)
    
    struct Queue<T> {
        private var queue: [T] = []
        
        var count: Int {
            queue.count
        }
        
        var isEmpty: Bool {
            queue.isEmpty
        }
        
        var peek: T? {
            queue.first
        }
        
        mutating func enqueue(_ element: T) {
            queue.append(element)
        }
        
        mutating func dequeue() -> T? {
            queue.isEmpty ? nil : queue.removeFirst()
        }
    }

  • 수도코드 1

    BFS(G, u)
        u.visited = true
        q.push(u);
        while(q.size()) 
            u = q.front() 
            q.pop()
            for each v ∈ G.Adj[u]
                if v.visited == false
                    v.visited = true
                    q.push(v) 

  • 수도코드 2 - 최단거리 배열로 쓸 수 있다.

    BFS(G, u)
        u.visited = 1
        q.push(u);
        while(q.size()) 
            u = q.front() 
            q.pop()
            for each v ∈ G.Adj[u]
                if v.visited == false
                    **v.visited = u.visited + 1**
                    q.push(v) 

• Swift 구현

  func bfs(v: Int) {
      var queue: [Int] = [v]
      visited[v] = 1
      
      while !queue.isEmpty {
          let u = queue.removeFirst()
          
          for node in graph[u]! { // 인접리스트니까 리스트가 항상 존재
              if visited[node] > 0 { continue }
              queue.append(node)
              visited[node] = visited[u] + 1 // 가중치가 같을 때, **최단거리 계산**
          }
      }
  }

• 시작지점이 다수인 경우

  • 큐에 푸시하는 지점도 다수가 되어야한다

  • 해당 지점들의 visited를 모두 1로 만들면서 시작해야한다.

• BFS가 가중치가 같은 그래프 내에서만 최단거리로 쓰이는 이유

  • Level로 최단거리를 측정하기 때문이다.

  • 현재 방법으로는 각 간선마다 다른 가중치를 줄 수 없다.

  • 가중치가 다른 경우의 최단거리를 찾기 위해서는 다익스트라, 벨만포드 등을 써야한다.

DFS와 BFS 비교

문제에서 "퍼져나간다", "탐색한다"가 있는 경우 DFS와 BFS를 우선적으로 떠올려보자.

가중치가 동일한 그래프에서 최단거리를 구할 땐 BFS를 사용하

• 시간복잡도 (동일하다)

  • 인접리스트: O(V + E)

  • 인접행렬 : O(V^2)

• 차이점

  • DFS

    • 메모리를 덜 사용한다.

    • 절단점 등을 구할 수 있다. (고급 알고리즘)

    • 코드가 간단하며, 완전탐색의 경우 많이 사용한다.

  • BFS

    • 큐를 구현해야하므로 메모리를 더 쓴다.

    • 가중치가 같은 그래프 내에서 최단거리를 구할 수 있다.

트리순회

트리 자료구조에서 각 노드를 정확히 한 번만 체계적으로 방문하는 알고리즘이다.

방문 순서에 따라 순회방법이 결정된다.

1. 후위순회(postorder traversal)

   • 자식들 노드 방문 후 자신을 방문한다. (왼쪽부터)

     postorder( node )
         if (node.visited == false) 
             postorder( node->left ) 
             postorder( node->right )
             node.visited = true

2. 전위순회 (preorder traversal)

   • 자신 노드 방문 후 자식 노드를 방문한다.

   • DFS와 동일하다.

     preorder( node )
         if (node.visited == false)
             node.visited = true
             preorder( node->left )
             preorder( node->right )

3. 중위순회 (inorder traversal)

   • 왼쪽 자식 노드 → 자신 노드 → 오른쪽 자식 노드

     inorder( node )
         if (node.visited == false) 
             inorder( node->left )
             node.visited = true
             inorder( node->right )

4. 레벨 순회

   • 같은 레벨을 탐색한다

   • BFS와 동일하다.

   var graph: [Int: [Int]] = [:]
   
   graph[1] = [2, 3]
   graph[2] = [4, 5]
   
   print("\\n후위 순회:", terminator: " ")
   postOrder(v: 1)
   
   print("\\n전위 순회:", terminator: " ")
   preOrder(v: 1)
   
   print("\\n중위 순회:", terminator: " ")
   inOrder(v: 1)
   
   func postOrder(v: Int?) { // 후위
       guard let v else { return }
       postOrder(v: graph[v]?[0])
       postOrder(v: graph[v]?[1])
       print(v, terminator: " ")
   }
   
   func preOrder(v: Int?) { // 전위
       guard let v else { return }
       print(v, terminator: " ")
       preOrder(v: graph[v]?[0])
       preOrder(v: graph[v]?[1])
   }
   
   func inOrder(v: Int?) { // 중위
       guard let v else { return }
       inOrder(v: graph[v]?[0])
       print(v, terminator: " ")
       inOrder(v: graph[v]?[1])
   }

다익스트라 알고리즘

개념

• 여러개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다.

• 음의 간선이 없을 때 정상적으로 동작한다. (0보다 작은 값을 가질 수 없다)

  • 현실 세계에서는 음의 간선으로 표현되지 않으므로 GPS 기본 알고리즘으로 채택되기도 한다.

알고리

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다. (최소힙 사용)

4. 최단 거리 테이블을 갱신한다.

코드

최소힙 코드

func dijkstra(_ start: Int) {
    // 최소 힙을 사용한다.
    var queue = Heap<Node>()
    
    // 방문 노드를 설정한다. - 최단 거리가 갱신된 경우 방문 처리한다.
    var visited = [Bool](repeating: false, count: v + 1)
    
    // Start -> start로 가는 경로는 0이다.
    result[start] = 0
    
    queue.push((Node(start, 0)))
    
    // pop은 nil을 리턴할 수 있도록 설계 되었다. 
    while let current = queue.pop() {
        let (node, cost) = (current.node, current.cost)
        guard !visited[node] else { continue }
        visited[node] = true
        
        if let edge = graph[node] {
            for next in edge {
                let (nextNode, nextCost) = (next.node, next.cost)
                
                guard !visited[nextNode] else { continue }
                
                // 기존 비용보다 더 짧은 비용으로 이동가능하다면, 최단 거리 테이블을 갱신한다.
                let newCost = cost + nextCost
                if newCost < result[nextNode] {
                    result[nextNode] = newCost
                    queue.push(Node(nextNode, newCost))
                }
            }
        }
    }
}