[Swift][알고리즘] 스위프트로 DFS 구현하기

안녕하세요. CalKim 입니다.

어제 카카오 공채 공고가 떴더라구요.

https://careers.kakao.com/2022-developer

2022 카카오 신입개발자 블라인드 채용

 

저는 코딩테스트 볼 때 DFS, BFS만 나오면 겁을 먹곤해서

언젠가 한 번 제대로 공부해야겠단 생각이 들었습니다.

그 언젠가가 바로 오늘인 것 같습니다. 캬컄캬캬컄

그런 의미에서 오늘은 스위프트를 이용하여 DFS 알고리즘을 구현해보도록 하겠습니다.

 

 

 

 

DFS 알고리즘이란

 

우선 간단히 DFS가 무엇인지 살펴보겠습니다.

DFS 는 Depth-First Search, 깊이 우선 탐색이라고 합니다.

 

이 방법은

그래프를 탐색할 때,

선택된 탐색방향으로 최대한 깊이 탐색을 하고

더 이상 깊어질 수 없을 때,

옆을 탐색합니다.

 

 

위와 같은 그래프가 있다고 하겠습니다.

이 그래프에서 깊이우선탐색을 적용하면,

 

 

위와 같이 한 방향으로 최대한 깊이 내려가고

3번에서 더 이상 갈 곳이 없으므로

 

 

옆을 탐색하게 됩니다.

 

 

또, 4번에서 더 이상 깊이 들어갈 수 없으므로,

하나씩 거슬러 올라가서 옆으로 빠질 길이 없나 살펴봅니다.

4번은 형제 노드가 더 이상 없으므로

2번의 형제 노드를 살피게 되고

마찬가지로 깊이 우선으로 탐색하게 됩니다.

 

 

따라서 이와 같은 순서로 탐색을 하게 됩니다.

 

 

 

 

DFS 구현하기 - 그래프 만들기

 

이번에는 위에서 만든 그래프를 구현하고 깊이우선탐색을 적용시켜보도록 하겠습니다.

 

우선 노드를 구성해주도록 하겠습니다.

각각의 노드는

부모노드와 자식 노드에 대한 정보를 가지고 있고,

탐색되었는지에 대한 프로퍼티가 있으면 될 것 같습니다.

 

class Node {
    var parent: Node?
    var child: [Node] = []
    var visited: Bool = false
}

따라서 노드는 위의 클래스와 같이 정의하였습니다.

 

 

이번에는 아래의 그래프 구성과 같이 노드를 만들겠습니다.

 

let a = Node()
let b = Node()
let c = Node()
let d = Node()
let e = Node()
let f = Node()
let g = Node()

a.child = [b,c]
b.child = [d,e]
c.child = [f,g]

음.... 왜 c 노드만 색깔이 다르게 나오는지는 모르겠지만....

시작 노드가 a라는 점만 알고 시작하도록 하겠습니다.

 

 

우선 DFS 함수의 틀을 잡아주었습니다.

func dfsSearch(_ startNode: Node) {
    //
}

 

 

startNode 를 받고나면 해당 노드의 visited 값을 true 로 바꿔줍니다.

그리고 함수 실행시 어떤 노드가 어떻게 바뀌는지 확인하기 위한 명령어를 넣도록 하겠습니다.

func dfsSearch(_ startNode: Node) {
    startNode.visited = true
    print("a: \(a.visited) b: \(b.visited) c: \(c.visited) d: \(d.visited) e: \(e.visited) f: \(f.visited) g: \(g.visited)")
}

 

 

이제부터 자식노드들을 살펴보기 시작합니다.

func dfsSearch(_ startNode: Node) {
    startNode.visited = true
    print("a: \(a.visited) b: \(b.visited) c: \(c.visited) d: \(d.visited) e: \(e.visited) f: \(f.visited) g: \(g.visited)")
    
    startNode.child.forEach({
    	//
    })
    
}

 

 

자식노드마다 dfsSearch를 재귀적으로 호출해줍니다.

그렇게되면 자식은 자식의 자식을, 그 자식은 또 자신의 자식을 살펴보며,

깊이우선 탐색이 적용됩니다.

func dfsSearch(_ startNode: Node) {
    startNode.visited = true
    print("a: \(a.visited) b: \(b.visited) c: \(c.visited) d: \(d.visited) e: \(e.visited) f: \(f.visited) g: \(g.visited)")
    
    startNode.child.forEach({
        dfsSearch($0)
    })
    
}

 

 

이것으로 깊이 우선 탐색 코드 작성이 끝났습니다.

실행시켜보도록 하겠습니다.

dfsSearch(a)

우리가 기대했던대로,

a, b, d, e, c, f, g 순서대로 탐색된 것을 확인할 수 있습니다.

 

 

이것으로 DFS를 재귀를 이용하여 구현해보았습니다.

막상 해보니까 크게 어렵지는 않은데,

재귀함수에 대한 부담감 때문에 그동안 부담스러워했던 것 같네요.

 

그럼 오늘 짠 DFS 코드 전문을 올리며 마치도록 하겠습니다.

읽어주셔서 감사합니다.

 

 

import Foundation

class Node {
    var parent: Node?
    var child: [Node] = []
    var visited: Bool = false
}

let a = Node()
let b = Node()
let c = Node()
let d = Node()
let e = Node()
let f = Node()
let g = Node()

a.child = [b,c]
b.child = [d,e]
c.child = [f,g]

func dfsSearch(_ startNode: Node) {
    startNode.visited = true
    print("a: \(a.visited) b: \(b.visited) c: \(c.visited) d: \(d.visited) e: \(e.visited) f: \(f.visited) g: \(g.visited)")
    
    startNode.child.forEach({
        dfsSearch($0)
    })
    
}

dfsSearch(a)

 

 

* 이 게시글에서 내용 상의 틀린 점 혹은 더 알아야 할 점 등이 있다면  알려주시면 감사히 배우겠습니다