Swift) 깊이 우선 탐색(DFS) 구현 해보기

 

안녕하세요 :) 소들입니다!!!

이번 포스팅에선 깊이 우선 탐색(DFS)에 대해 알아보려고 해요!!!!

깊이 우선 탐색이란, 너비 우선 탐색(BFS)과 마찬가지로 그래프를 탐색하는 방법 중 하나인데,

그래프를 모르면 이해할 수 없으니, 혹시 그래프를 모르면 이 포스팅을 꼭! 먼저 읽고 와주세요

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 깊이 우선 탐색(DFS)이란?

 

깊이 우선 탐색이란 Depth-First Search로,

보통 DFS라고들 많이 부름!!! :) 머 정의는 다음과 같은데..

 

탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식

 

음.. 정의만 보면 역시 이해가 안 갈 테니까:)

깊이 우선 탐색 방식에선,  다음과 같은 순서로 그래프의 노드를 탐색함!!

 

 

 

 

숫자가 순서라고 생각하면 됨!!!

탐색 노드의 인접 노드의 자식 노드들을 모두 탐색하고,

다시 돌아가서 탐색 노드의 다른 인접 노드 자식들을 모두 탐색하는 방법임

 

참고로 깊이 우선 탐색 또한 내 인접 노드들 중에서,

왼쪽을 먼저 탐색하냐, 오른쪽을 먼저 탐색하냐 같은 순서는 중요하지 않음!

어디를 먼저 탐색하더라도, 해당 노드의 가장 깊은 노드까지 우선 다 탐색해야 다음 인접 노드를 탐색할 수 있음!

 

 

 

 

2. 코드로 구현 해보기

 

2-1. 탐색할 그래프 미리 만들어두기

 

음.. ~ 여기서 또한 데이터를 갖고 그래프를 어떻게 구현하냐!는 다루지 않음

다만, 이미 구현되어 있는 그래프를 어떻게 탐색하는지만 다룰 것임 :)

 

따라서, 탐색할 그래프를 미리 딕셔너리 형태로 만들어 두겠음

그래프를 표현하는 방법엔 두 가지 방법이 있다고 이전전 포스팅에서 배웠음!

그중에 인접 리스트 방식으로 다음과 같이 나타낼 수 있고,

 

 

 

 

이를 하드코딩으로 하면..ㅎ

 

 

let graph: [String: [String]] = [
    "A" : ["B", "C"],
    "B" : ["A", "D", "E"],
    "C" : ["A", "F"],
    "D" : ["B"],
    "E" : ["B"],
    "F" : ["C"],
]

 

 

요롷게..ㅎ

(+ 너비 우선 탐색과 거의 똑같으나 Queue or Stack 부분만 달라서

포스팅좀 재탕하겠음^^;)

 

 

 

2-2. 깊이 우선 탐색을 하는 방법

 

깊이 우선 탐색은 보통 한 개의 큐(Queue)와, 한 개의 스택(Stack)으로 구현함!!!!

 

방문 해야하는 노드를 저장하는 Stack(이하,needVisitStack)

이미 방문한 노드를 저장하는 Queue(이하, visitedQueue)

 

이렇게 두 가지 큐로 구현할 수 있음!!

너비 우선 탐색과 달리, 방문 해야하는 노드를 Stack으로 저장함 :)

 

 

 

 

이렇게 👀

자 만약 A부터 탐색을 한다고 하면, 어떤 방식으로 탐색하는지 봐볼 것임

 

 

 ① 탐색할 노드의 데이터를 needVisitStack에 넣는다 

 

 

 

 

 ② needVisitStack의 마지막 값을 추출해서(LIFO), visitedQueue에 해당 값이 존재하는지 확인한다 

 

 

 

 

만약, visitedQueue에 추출한 값이 존재하면,

추출한 값은 버리고 그 다음 마지막 값을 다시 추출(LIFO)하여, visitedQueue에 존재하는지 확인함

위 과정을 visitedQueue에 존재하지 않는 값이 나올 때까지 반복하는데,

그러다가 needVisitStack이 텅~ 비면 그때 탐색이 끝나는 것임:)

 

근데, 만약 위처럼 visitedQueue에 추출한 값이 존재하지 않으면 다음 ③번 과정을 진행함!

 

 

 ③ 추출된 값이 visitedQueue에 존재하지 않으면, visitedQueue에 추가한다 

 

 

 

 

 ④ 추출된 값(방금 visitedQueue에 추가된 값)에 연결된 간선들을

모두 needVisitStack에 추가한다 

 

 

 

 

위 작업까지 했으면,

needVisitStack이 빌 때까지 다시 ②번부터 반복함

 

 

.

.

한번 따라서 쭉 ~ 해보셈!! 그럼 마지막엔 visitedQueue에 다음과 저장되어 있을 것임 :)

 

 

 

 

needVisitStack이 모두 비었을 경우, visitedQueue에 채워진 값들이

깊이 우선 탐색을 통해 탐색된 노드들의 순서임 :)

 

왜 A-B-D-E-C-F 가 아니라, A-C-F-B-D-E냐면,

깊이 우선 탐색엔 처음 탐색 노드의 어떤 인접 노드부터 탐색할지는 순서가 없음!

다만, B를 고르던 C를 고르던, 가장 깊은 자식 노드까지 다 탐색해야 다음 인접 노드를 탐색할 수 있을 뿐

 

 

 

2-3. (이번엔 진짜) 코드로 구현하기

 

탐색할 그래프를 위에서 만든 것을 쓴다고 하면,

깊이 우선 탐색은 다음과 같이 구현할 수 있음 :)

 

 

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
}

 

 

너비 우선 탐색하고 코드 똑같음!!!!!!! 그러나 어디만 바꼈냐면,

removeFirst가 아닌 removeLast임!! 왜냐??

스택이라 LIFO니까! 가장 마지막 녀석을 꺼내야 하니까 :)

 

 

 

 

3. 깊이 우선 탐색(DFS)의 시간 복잡도

 

일반적으로 노드 수(V), 간선 수(E)라 했을 때 시간 복잡도는

 

O(V+E)

 

가 됨...! 입력 자체를 노드와 간선으로 받기 때문에..👀

 

 

 

 

 

.

.

.

깊이 우선 탐색은 재귀함수로도 짤 수 있다 하는데,

가장 정석적인 방법으로 짜봤어여 :) 

혹시 피드백, 이해 안 가시는 점은 언제든 댓글 남겨주세요~~