DFS / BFS 1편

들어가며...

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다.
대표적으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다.
이를 제대로 이해하기 위해서는 자료구조인 스택과 큐를 이해하고, 재귀 함수에 대해 알아야 하기 때문에 본격적인 설명에 앞서 간단히 정리해보자.

자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.
스택과 큐는 기초 개념으로 다음 두 핵심 함수로 구성되어 있다.

• 삽입(push): 데이터를 삽입한다.
• 삭제(pop): 데이터를 삭제한다.

이러한 자료구조를 활용할 때는 오버플로와 언더플로에 대한 예외처리를 해주어야 한다.

스택

스택은 굉장히 간단하다. 영어 단어에서 유추할 수 있는데, 책 쌓기를 떠올리면 이해가 쉽다.
책을 바닥에서부터 한권씩 차곡차곡 쌓는 상황을 생각해보자.
이 상황에서 책을 한권씩 빼려고 하는데 맨 아래있는 책을 빼기 위해서는 굉장히 힘이 많이 들 것이다. 위에 있는 책들을 먼저 다 빼면 맨 아래에 있는 책을 빼기 쉬울 것이다. 이러한 상황에서 아래에 있는 책을 빼기 위해서 위에 있는 책을 먼저 빼야 한다고 정리할 수 있다.
이러한 구조를 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 구조라고 한다.

Swift에서 스택을 구현하는 것은 굉장히 간단하다.
Array를 활용해주면 된다.

정리하면,

스택은 LIFO(Last In First Out)의 특징을 가지는 자료구조이다. 스택은 자료를 저장할 때, 먼저 넣은 데이터를 가장 마지막에 꺼내게 된다. 스위프트의 배열은 스택과 동일한 append, removeLast 메서드를 지원하기 때문에 배열을 한 번 감싸주는 자료구조를 구현하면 쉽게 만들 수 있다.

큐

큐는 대기열에 비유할 수 있습니다. 우리가 유명 맛집에 들어가기 위해 줄을 설 때, 먼저 온 사람이 식당에 먼저 들어간다. 나중에 온 사람은 나중에 들어가게 된다. 이러한 구조를 FIFO(First In First Out) 구조라고 한다.

Swift에서 큐가 따로 없기 때문에 직접 구현해주어야 한다.
큐를 구현하는 방법은 다양하지만, 필자의 경우 Double Stack을 활용해서 큐를 구현한다.
여기서 이런 생각을 할 수 있다.

그냥 배열로 만들어서 `insert(:at:), removeFirst(:)` 사용하면 되는거 아닌가?

물론 맞는 말이다. 처맞는 말.
insert(_:at:0), removeFirst(_:) 을 사용하면 시간복잡도가 O(N)이다. 그래서 성능이 매우 안좋아지기 때문에 직접 구현해서 사용해야 한다.

직접 구현한 큐를 보면서 얘기해보자.

final class Queue<T> {
	private var enqueueStack: [T] = []
    private var dequeueStack: [T] = []
    
    var isEmpty: Bool {
    	enqueueStack.isEmpty && dequeueStack.isEmpty
    }
    
    var count: Int {
    	enqueueStack.count + dequeueStack.count
    }
    
    var peek: T? {
    	dequeueStack.isEmpty ? enqueueStack.first : dequeueStack.last
    }
    
    func enqueue(_ item: T) {
    	enqueueStack.append(item)
    }
    
    func dequeue() -> T? {
    	if dequeueStack.isEmpty {
        	dequeueStack = enqueueStack.reversed()
            enqueueStack.removeAll(keepingCapacity: true)
        }
        return dequeuStack.popLast()
    }
    
}

위와 같이 큐를 Double Stack을 활용해서 구현하면
enqueue(_:), dequeue() 단계에서 시간복잡도 O(1)로 활용이 가능하다.

정리하자면,

큐는 FIFO(First In First Out)의 특성을 가지는 자료구조이다. 이름처럼 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 특징을 가지고 있다. 스위프트에서는 배열에서 removeFirst를 지원하긴 하지만, 시간복잡도는 O(n)이라서, 동작만 FIFO일 뿐, 삭제에 O(1)을 보장하는 큐가 될 수는 없다. 그래서 직접구현을 통해 큐를 만들어 사용한다.

재귀 함수

재귀 함수란 자기 자신을 다시 호출하는 함수를 의마한다.
예제를 보면 빠르게 이해할 수 있다.

func recursiveFunction() {
	print("재귀 함수를 호출해보자.")
    recursiveFunction()
}
recursiveFunction()

위의 코드를 실행하면 "재귀 함수를 호출해보자." 라는 문자열이 무한히 출력된다.
무한. 이 단어는 우리는 조심해야한다. while 문을 생각해보면 while 문은 특정 조건을 만족하면 무한히 반복했다. 그래서 우리는 특정 조건에 위배되도록 즉, break를 걸어줄 수 있는 장치를 넣어주어야 했다.
재귀 함수 역시 마찬가지다. 항상 재귀 함수를 사용한다면 종료 조건을 만들어야 한다.

func recursiveFunction(_ n: Int) {
	if n == 6 {
    	return
    }
	print("n")
    recursiveFunction(n + 1)
}
recursiveFunction(1)

위와 같이 재귀 함수를 작성하면 1, 2, 3, 4, 5까지 출력될 것이다.

컴퓨터 내부에서 함수는 스택 자료구조를 이용한다. 그렇기 때문에 재귀 함수의 수행은 스택에서 처럼 마지막에 호출한 함수의 수행이 끝내야 그 전 함수가 종료될 수 있다.

정리하자면,

재귀 함수는 자기 자신을 호출하는 함수이다. 그렇기 때문에 종료 조건을 넣어주지 않으면 함수가 무한히 호출되어 멈추게 된다. 재귀 함수의 수행은 스택 자료구조를 이용하기 때문에 마지막에 호출한 함수의 수행이 끝내야 그 전 함수가 종료될 수 있다.

마무리

DFS / BFS를 배우기 전, 알고 있어야할 기본 지식인 스택, 큐, 재귀 함수에 대해 알아봤다.
2편부터는 본격적으로 DFS / BFS에 대해 알아볼 것이다.
DFS / BFS는 알고리즘 문제를 풀 때 자주 만날 수 있기 때문에 한 번 제대로 이해하면 편할 것이다.

그럼 안녕히.