[1] Swift Algorithm DFS

DFS(Depth Frist Search)는, 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

그림을 보고 이해해 보도록 하자.

위와 같은 그래프 이미지에서 회색 원은 노드라고 하고, 노드 끼리 연결된 검정색 선은 간선 이라고 한다.

각 노드에서 다른 노드로 이동하기 위해서는 해당 간선을 통해서만 이동할 수 있다고 생각하면 된다.

DFS의 이름 처럼 각 노드의 가장 깊은 곳을 먼저 탐색하려 하기 때문에, 위와 같은 그래프에서는 아래의 그림과 같이 탐색할 수 있다.

(DFS를 이용해서 탐색할 경우 통상적으로는 수가 낮은 순서부터 처리하도록 구현 한다고 한다.)

1 -> 2 -> 4

1 -> 2 -> 5

1 -> 3

result : 1 -> 2 -> 4 -> 5 -> 3

그럼 이를 어떻게 코드로 표현할 수 있을까?

우선은 그래프를 구현하는 것 부터 시작될 수 있을 것 같다.

크게 두가지 방법이 있을 것 같은데,

1. 2차원 배열을 이용하여 구현

2. 인접 리스트 방식으로 구현

1. 2차원 배열을 이용하여 구현

해당 방식은, 인접행렬을 이용해서 구현하는 방식이다.

우선 해당 그래프에서는 딱히 방향을 지정해주지 않았다는 점을 고려해서 행렬을 만들게 되면 아래 그림과 같이 만들어 줄 수 있다.

이를 Swift Array로 나타내면 다음과 같다. (연결되지 않은 항목은 Int.max로 표현 하였고 가중치는 1로 가정한다. 자기 자신일땐 0으로 표현하였다.)

var graph: [[Int]] = [
    [0, 1, 1, Int.max, Int.max],
    [1, 0, Int.max, 1, 1],
    [1, Int.max, 0, Int.max, Int.max],
    [Int.max, 1, Int.max, 0, Int.max],
    [Int.max, 1, Int.max, Int.max, 0]
]

2. 인접 리스트 방식으로 구현

인접 리스트 방식은, 링크드 리스트 방식이라고 생각하면 된다.

각 노드가 어떤 연관 관계를 가지고 있는지 (연관, 가중치)와 같은 튜플 형태의 배열로 나타낼 수 있다.

var graph: [[(Int, Int)]] = [
    [(2, 1), (3, 1)],
    [(1, 1), (4, 1), (5, 1)],
    [(1, 1)],
    [(2, 1)],
    [(2, 1)]
]

표현이 가능한 형태로 나타냈으니 이제 직접 그려보며 결과라고 예측했던 내용 result : 1 -> 2 -> 4 -> 5 -> 3처럼 나오는지를 dfs를 이용하여 직접 구현해보겠다.

3. DFS 구현

그래프 형태를 올바르게 만들었으니 어떤식으로 깊은 곳 부터 찍고 순회하며 찾을 수 있을지에 대해서 고민해야 한다.

핵심은 이미 가본 곳은 다시 찾아보지 않고 가지 않은 깊은 곳 부터 순회한다 이다.

이 핵심을 지키기 위해서는 이미 가본 곳을 기록할 필요가 있다.

인접행렬의 경우

아래 코드와 같이 visited 배열을 만들어, 이미 검색한 곳을 기록하여 중복으로 검색하지 않도록 한다.

실제 함수 구현은 재귀적으로 작동되게 구현하였는데 함수의 흐름을 전반적으로 따라가면 다음과 같다.

1. startingIndex -> 0이기 때문에 vistedArray는 [true, false, false, false] 가 된다.

2. graph[0][0]인 1번 노드 의 경우에는 2번, 3번 과 연관이 있는데, 첫번째는 자기 자신이기 때문에 반복문에서 아무일도 일어나지 않는다.

3. graph[0][1]은, 그래프 그림에서의 (2) 즉 2번을 나타내고, visitedArray[1]은 아직 false이기 때문에 해당 그래프의 아래로 내려가기 위해 다시한번 dfs 함수를 재귀적으로 호출하게 된다.

4. visitedArray의 값은 [true, true, false, false, false]가 되고, 이때 바라 보는 값은 1번 혹은 4번, 5번 이다.

5. 0번째 인덱스의 경우에는 이미 탐색했기 때문에 무시되고, 다음 원소들을 고려하다가 index상으로 3인 4번을 탐색하게 된다. (visited[3] = false이기 때문)

6. 위와 같은 방식을 반복하게 되면 이미 검색한 원소는 무시되고, 해당 원소와 연관이 있는 깊은 원소만을 탐색할 수 있기 때문에 깊이 우선 탐색을 수행할 수 있다.

var graph: [[Int]] = [
    [0, 1, 1, Int.max, Int.max],
    [1, 0, Int.max, 1, 1],
    [1, Int.max, 0, Int.max, Int.max],
    [Int.max, 1, Int.max, 0, Int.max],
    [Int.max, 1, Int.max, Int.max, 0]
]

var visited: [Bool] = Array.init(repeating: false, count: graph.count)

func dfs(startIndex: Int) {
    visited[startIndex] = true
    
    for (index, node) in graph[startIndex].enumerated() {
        if node != Int.max, !visited[index] {
            print(index + 1)
            dfs(startIndex: index)
        }
    }
}

dfs(startIndex: 0)

인접 리스트의 경우

동일한 그래프 형태이기 때문에 위의 구현과 유사하다.

각 그래프에서 이미 방문한 node를 무시하고, 해당하는 튜플의 첫번째 원소를 이용하여 각 리스트 간의 DFS를 구현할 수 있다.

var graph: [[(Int, Int)]] = [
    [(2, 1), (3, 1)],
    [(1, 1), (4, 1), (5, 1)],
    [(1, 1)],
    [(2, 1)],
    [(2, 1)]
]

var visited: [Bool] = Array.init(repeating: false, count: graph.count)

func dfs(startIndex: Int) {
    visited[startIndex] = true
    
    for node in graph[startIndex] {
        if !visited[node.0 - 1] {
            print(node.0)
            dfs(startIndex: node.0 - 1)
        }
    }
}

dfs(startIndex: 0)

사실 이렇게만 본다면 DFS가 그렇게 어려운 개념은 아니라고 생각한다.

다만 실제 문제에 위의 코드를 그대로 적용하기에는 어려운 경우들이 있어 위와 같은 케이스들을 알아보려 한다.