[Swift] DFS(Depth-First Search, 깊이 우선 탐색)에 대해서 알아보자

안녕하세요~

 

오늘은 깊이 우선 탐색에 대해서 정리하려고 합니다.

 

 

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

 

깊이 우선 탐색은 탐색하고자 하는 노드들의 자식 노드부터 우선으로 탐색하는 방식을 말합니다. 

 

아래의 이미지에 있는 그래프에서 BFS를 사용하면

 

 

앞서 말한 것처럼 자식 노드부터 확인하는데 

예를 들어서 1을 가장 먼저 탐색하고 나면 8, 6, 10, 7, 4 ... 을 순서대로 탐색하게 됩니다.

 

즉, 탐색하고자하는 노드의 자식 노드들을 모두 탐색하는 방법입니다.

 

BFS와 마찬가지로 여기서 8부터 시작하든 2부터 시작하든 순서는 중요하지 않습니다. 

중요한 점은 자식 노드들을 우선 탐색해야 한다는 것입니다.

 

✔︎ Swift로 구현해 보기

위의 이미지에 있는 그래프를 통해 DFS를 구현해 보자.

 

1. 큐( Queue )

 

DSF는 보통 한 개의 큐와 한 개의 스택으로 구현합니다.

 

(1) 방문한 노드를 저장하는 큐

(2) 방문해야 하는 노드를 저장하는 스택

 

BFS에서는 두개의 큐를 사용했는데

DFS에서 스택을 사용하는 이유는 간단합니다.

 

BFS에서는  Queue의 FIFO 성질을 이용해 인접리스트에서 depth가 가장 낮은 노드를 가지고 올 수 있는 것이고

DFS에서는 Stack의 LIFO 성질을 이용해 인접리스트에서 depth가 가장 깊은 노드를 가지고 올 수 있는 것입니다.

 

위의 이미지를 예로 들어보겠습니다.

 

"1"을 가장 먼저 선택해 탐색하면

 

1. BFS

 

	visitQueue	needVisitQueue
루프 1	["1"]	["8", "5", "2"]
루프 2	["1", "8"]	["2", "5", "6", "4", "3"]
루프 3	["1", "8", "5"]	["2", "6", "4", "3"]

 

위와 같이 큐를 이용하게되면 같은 depth부터 탐색이 가능해집니다.

 

2. DFS

 

	visitQueue	needVisitStack
루프 1	["1"]	["2", "5", "8"]
루프 2	["1", "8"]	["2", "5", "3", "4", "6"]
루프 3	["1", "8", "6"]	["2", "5", "3", "4", "7", "10"]

 

위와 같이 스택을 사용하면 depth가 더 깊은 노드부터 탐색이 가능해집니다.

 

큐와 스택은 지난 포스팅에서 다뤘으니 참고하시면 좋을 것 같습니다.

 

[ 큐(Queue) ]

 

[Swift] 자료구조 - 큐(Queue)

[ 스택(Stack) ]

 

[Swift] 자료구조 - 스택(Stack)

 

2. 인접리스트( Adjacency List )

 

그래프를 표현하는 방법에는

인접 행렬 그래프와 인접 리스트 방식 두 가지가 존재합니다.

 

여기서는 인접 리스트 방식을 사용해 설명하겠습니다.

인접리스트란 말 그대로 인접한 노드들을 리스트로 나열한 것을 말합니다.

 

1	8	5	2
8	1	6	4	3
5	1
2	1	9
6	8	10	7
4	8
3	8
9	2
10	6
7	6

 

위의 값들을 딕셔너리로 구현하면 아래와 같습니다.

 

let graph: [String: [Int]] = [
    "1" : [8, 5, 2],
    "8" : [1, 6, 4, 3],
    "5" : [1],
    "2" : [1, 9],
    "6" : [8, 10, 7],
    "4" : [8],
    "3" : [8],
    "9" : [2],
    "10" : [6],
    "7" : [6]
]

 

3. DFS

설명은 주석으로 하겠습니다.

 

func depthFirstSearch(graph: [String: [Int]], start: String) -> [String] {

    // 이미 방문한 노드를 저장하는 큐
    var visitedQueue: [String] = []
    // 방문해야하는 노드를 저장하는 스택
    var needVisitStack: [String] = [start]
    
    while !needVisitStack.isEmpty {
        
        let node: String = String(needVisitStack.removeLast())
        
        // 이미 방문했던 노드라면 continue 처리
        if visitedQueue.contains(node) {
            continue
        }
        
        visitedQueue.append(node)
        // 인접 노드를 추가하는 과정
        // 만약 가장 처음에 "1"이 들어온다면 1과 인접한 리스트를 needVisitStack에 추가하는 과정
        needVisitStack += graph[node].map{ $0.map { String($0) } }?.reversed() ?? []
    }
    
    return visitedQueue
}

print(depthFirstSearch(graph: graph, start: "1"))
// ["1", "8", "6", "10", "7", "4", "3", "5", "2", "9"]

 

여기까지 정리하겠습니다.

그럼 이만 👋🏻 👋🏻 👋🏻