[Algorithm] Swift로 보는 DFS 원리부터 뽀개기 <1>

Swift 로 푸는 DFS, BFS 문제풀이 원리 학습

나동빈의 이것이 코딩테스트다의 내용을 기반으로 작성하였습니다!!

<1> 꼭 필요한 자료구조 기초

Stack 자료구조

Stack은 박스를 아래서 위로 쌓는다는 느낌으로 선입후출(FILO) 구조를 상상하면 된다.
순서가 중요한 경우에 사용하면 좋다.

삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제() -> 삽입(1) -> 삽입(4) -> 삭제()

[5]
[5, 2]
[5, 2, 3]
[5, 2, 3, 7]
[5, 2, 3]
[5, 2, 3, 1]
[5, 2, 3, 1, 4]
[5, 2, 3, 1]

append()와 pop()을 활용해서 맨 뒤의 데이터만 관리해 주면 된다.

---

Queue 자료구조

Queue 는 대기줄에 비유할 수 있다. 먼저 도착하면 먼저 탑승하듯이, 선입선출(FIFO) 구조를 가지고 있다.

삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제() -> 삽입(1) -> 삽입(4) -> 삭제()

[5]
[2, 5]
[3, 2, 5]
[7, 3, 2, 5]
[7, 3, 2]
[1, 7, 3, 2]
[4, 1, 7, 3, 2]
[4, 1, 7, 3]

deque([4, 1, 7, 3])
deque.reverse() // [3, 7, 1, 4]

먼저들어간 녀석이 대기줄의 마지막 녀석이 된다. 마지막 녀석을 빼주면 선입선출 구조 완성!

---

재귀함수

재귀함수란 자기 자신을 자기 내부에서 또 호출하는 함수입니다.
팩토리얼을 구현하는 식을 세워 보겠습니다.

//반복식으로 구현한 팩토리얼
func iterative(n: Int) {
    result = 1 

    for i in 0..<n {
        result *= i
    }

    return result
}

//재귀적으로 구현한 팩토리얼
func recursive(n: Int) {
    if n <= 1 {
        return 1
    }

    return n * factorial(n - 1)
}

---

<2> 탐색 알고리즘 DFS

DFS(Depth-First Search)

깊이 우선 탐색은 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘

그래프란 노드(node)와 간선(edge)로 표현되며 이때 노드를 정점(vertex)이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 말한다.

프로그래밍에서는 그래프를 두 가지 방식으로 표현한다.

인접행렬

인접행렬은 2차원의 배열로 그래프의 연결관계를 표현한다.
배열 안의 배열 형태라고 생각하면 된다.

예를 들어 0번 노드와 1번, 2번 노드는 각각의 간선(간선 7, 5)으로 연결되어 있는 형태라고 하면, 인접 행렬방식으로는 아래와 같이 표현한다.

let inf = 9999999
var graph = [
    [0, 7, 5],
    [7, 0, inf],
    [5, inf, 0]
]

인접행렬 방식은 2차원의 배열에 각 노드가 연결된 형태를 기록하는 방식. 연결이 되어있지 않은 노드끼리는 무한으로 작성한다.

인접리스트

인접 리스트 방식에서는 데이터를 노드와 연결된 노드에 대한 정보를 차례로 연결하여 저장한다.

이 경우에는

var graph = [
    [(1, 7), (2, 5)], 
    // 0번 노드는 터플의 0번 자리인 노드에 터플의 1번자리인 간선으로 연결되어있다
    [(0, 7)],
    [(0, 5)]
]

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

먼저 인접 행렬은 연결되어 있지 않은 경우도 모두 표기하기 때문에 불필요하게 메모리가 사용된다는 단점이 있다. 반면 인접리스트의 경우 연결된 정보만을 저장하기 때문에 메모리 면에서 더욱 효율적이다.

하지만 인접리스트의 경우, 특정 노드와 노드가 연결되어있는지를 확인하기 위해서 무조건 리스트를 돌아야 하므로 이 경우 불리하다.

만약 노드 1과 노드 7이 연결되어있는지 확인하고자 한다면, 인접행렬 방식에서는 graph[1][7]만 확인하면 된다. 그러나 인접 리스트 방식에서는 노드1에 대한 인접 리스트를 앞에서부터 모두 확인해야한다. 모든 노드를 순회해야만 하는 경우에 인접 리스트를 활용하면 된다.

DFS는 탐색을 위해 사용되는 탐색 알고리즘이다. 이것의 작동방식은 다음과 같다.

Depth-First 방식이기 때문에 노드에 연결된 가장 깊은 연결고리까지 들어가 마지막 노드를 방문한 후에 다음 경로를 찾는 알고리즘이다.

DFS 동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더이상 수행할 수 없을 때 까지 반복한다.

DFS를 예제로 살펴보면 다음과 같다. 개발자 소들이님 예제 참고

func DFS(graph: [String: [String]], start: String) -> [String] {
    var visitedQueue: [String] = []
    var needVisitStack: [String] = [start]

    while !needVisitStack.isEmpty {
        let node: String = needVisitStack.removeLast()
        if visitedQueue.contains(node) { continue }

        visitedQueue.append(node)
       needVisitStack += graph[node] ?? []
    }

    return visitedQueue
}

먼저 이미 방문한 queue와 앞으로 방문해야 하는 스택을 각각 만들어 준다. 방문해야 하는 스택에는 초기값으로 start를 넣어준다.

방문하지 않은 스택이 비어있지 않은 상태, 즉 방문해야 하는 노드가 아직 존재하는 상태일 때, 확인해야 할 노드의 맨 마지막 요소를 넣어준다. 이 노드는 아직 방문한 큐에 들어있지 않기 때문에, 해당 노드를 visitedQueue에 append해준다. 그리고 방문해야 할 스택에는 그래프 내에 해당 노드의 값으로 지정된 배열을 다시 넣어준다.

방문해야 하는 스택의 마지막 값을 다시 노드에 넣어주고 방문한 큐에 존재하면 버려준다. 없으면 append해주고 해당 노드에 연결된 배열을 다시 넣어준다. 이 과정을 다 마치게 되면 빈 값을 넣어주고 while 문을 종료한다.

이렇게 되면 모든 노드를 방문하게 된다. 즉 모든 노드를 다 탐색하게 되는 것이다.

---

학습한 내용을 정리하고 있는 Github 주소를 공개합니다.
Star를 해두시면 건강에 좋습니다!

GitHub - AnnaBaeTofuMom/TodayILearned: 새롭게 배운 것을 기록합니다, 나의 언어로 새로 씁니다.