기초 개념GitHubBeakjoon

그래프 탐색

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

그래프 개념

정점과 간선

  • 정점 (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))
                }
            }
        }
    }
}
Previous수학 공식NextSorting

Last updated