[Swift] 그래프와 탐색 알고리즘 DFS/BFS (설명 및 구현 예제)

[Swift] 그래프와 탐색 알고리즘 DFS/BFS

가장 도움이 된 글.. https://nareunhagae.tistory.com/56 🙏
'이것이 코딩 테스트다' 책도 함께 참고해 작성했습니다.

그래프 Graph

그래프에서는 모든 객체는 정점(노드)로 나타내고, 모든 관계는 간선으로 나타낸다.

• 노드 Node / 정점 Vertex
  • 그래프에서 데이터를 담는 단위. (그림에서의 동그라미 = 노드)
  • 두 노드가 인접하다adjacent : 두 노드가 간선으로 연결되어 있음을 의미
• 간선 Edge
  • 노드 사이를 잇는 선.
• 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것

알고리즘 문제 중 1차원 배열, 2차월 배열 탐색 문제를 그래프 형태로 생각하면 문제를 쉽게 풀 수 있다.

그래프 표현

프로그래밍에서 그래프를 표현하는 방식.

1. 인접 행렬 Adjacency Matrix : 2차원 배열로 그래프의 각 노드의 연결관계 표현

   1. 예를 들어 위 그래프는 [[0, 7, 5], [7, 0, Int.max], [5, Int.max, 0]] 과 같이 표현한다.
   2. 자신과의 거리는 0, 간선이 있으면 간선의 가중치, 간선이 없으면 무한과 같이 정답이 될 수 없는 큰 값을 넣는다.
   3. 장점 : 특정 노드가 연결되어 있는지 확인하는 것이 빠르다.
   4. 단점 : 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.

2. 인접 리스트 Adjacency List : 배열/리스트로 그래프의 각 노드의 연결관계 표현

   1. 위 그래프에서 배열의 인덱스가 노드의 값이라고 생각했을 때, 아래와 같이 표현 가능 (2차원배열)

       let graph = [
           [1, 2],
           [0],
           [0]
       ]

   2. 위 그래프에서 [노드 : [인접노드]] 로 생각했을 때, 아래와 같이 표현 가능 (딕셔너리)
      (그래프 표현 방식에도 여러 가지가 있는 것 같다. 예를 들어 가중치가 있는 경우는 이와 다르게 표현해야 할듯..)

       let graph: [Int: [Int]] = [
           0 : [1, 2],
           1 : [0],
           2 : [0]
       ]

   3. 장점 : 연결된 정보만을 저장하므로 메모리를 효율적으로 사용한다. 특정 노드와 인접한 모든 노드를 순회해야 하는 경우, 인접 리스트 방식이 메모리 낭비가 적다.

   4. 단점 : 특정 노드가 연결되어 있는지 확인하는 속도가 느리다. - 연결 데이터를 하나씩 확인해야 하므로

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

• 자식 노드부터 탐색하는 방식.
• 멀리 있는 노드부터 탐색하는 알고리즘. (그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘)
• 방문 처리 : 한 번 처리한 노드를 다시 처리하지 않도록 체크하는 것.
• 스택 자료구조에 기초한다.
• 재귀를 이용하면 간결하게 구현할 수 있다.
• O(n) 의 시간복잡도를 가진다. (n = 데이터의 개수)

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
   1. 만약 인접 노드 중 방문하지 않은 노드가 여러 개면, 값이 낮은 노드를 먼저 스택에 삽입한다.
3. 정답을 찾거나 모든 노드를 탐색할 때까지 2.를 반복한다.
   1. 정답을 찾았다면 탐색을 멈춘다.

https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbkblwn%2FbtqRePH03Vp%2FKIuJbqhfy0tKXNBFk9hIDK%2Fimg.jpg

예를 들어 위 그래프를 DFS로 탐색한다면,

탐색 순서는 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5 가 된다.

DFS 구현

let graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

var visited = Array(repeating: false, count: graph.count)

func dfs(graph: [[Int]], start: Int) {
    visited[start] = true // 시작점

    print(start, terminator: " ")

    for i in graph[start] { // 왼쪽부터 순회
        if !visited[i] {
            dfs(graph: graph, start: i)
        }
    }
}
// 1 2 7 6 8 3 4 5

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

• 인접한 노드들을 우선 탐색하는 방식.
• 가까운 노드부터 탐색하는 알고리즘.
  • 1950년 미로를 탈출하는 가장 짧은 경로를 찾기 위해 탄생한 알고리즘이다.
• 큐를 사용해 구현하는 것이 정석이다.
  • 인접 노드를 큐에 넣으면 자연스럽게 선입선출이 되어 가까운 노드부터 탐색하게 된다.
• O(n) 의 시간복잡도를 가진다. (n = 데이터의 개수)
• 일반적인 경우 실제 수행 시간은 DFS보다 BFS가 빠른 편이다.

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.
2. 큐에서 노드를 꺼내, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
   1. 만약 인접 노드 중 방문하지 않은 노드가 여러 개면, 값이 낮은 노드 or 왼쪽 노드를 먼저 큐에 삽입한다.
3. 정답을 찾거나, 모든 노드를 탐색할 때까지 2.를 반복한다.
   1. 정답을 찾았다면 탐색을 멈춘다.

https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbkblwn%2FbtqRePH03Vp%2FKIuJbqhfy0tKXNBFk9hIDK%2Fimg.jpg

예를 들어 DFS와 같은 그래프를 BFS로 탐색한다면,

탐색 순서(큐에 들어간 순서)는 1 -> 2 -> 3 -> 8-> 7 -> 4 -> 5 -> 6 이 된다.

BFS 구현

let graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

func bfs(graph: [[Int]], start: Int) {
    var queue = Queue<Int>()
    var visited = Array(repeating: false, count: graph.count + 1)

    queue.enqueue(start)
    visited[start] = true

    while !queue.isEmpty {
        guard let key = queue.dequeue() else { return }

        print(key, terminator: " ")
        for i in graph[key] {
            if !visited[i] {
                queue.enqueue(i)
                visited[i] = true
            }
        }
    }
}

// 1 2 3 8 7 4 5 6