[알고리즘] 깊이 우선 탐색 chapter.01

이번주 알고리즘 주제로 깊이 우선 탐색이 나왔다. 캠프에 합류하기 직전 한번 떨어져나 보자 싶어 지원했던 기업 코딩테스트에서 손도 대지 못한 문제가 있었다. 지원자들 오픈톡방에 2번 문제 푸신 분 어떻게 푸셨나요? 물어봤더니 몇몇 분들이 dfs, bfs로 푸시면 됩니다. 라고 답을 해주셨는데 도대체 저게 무슨 말이냐 이 세상에 저런 단어도 있었냐 라고 생각했던 바로 그 주제다. 그 당시에 한번 검색해본 뒤 내가 당장 이해할 수 있는 영역이 아닌 것 같아서 떠나보냈는데, 이렇게 금방 또 맞닥뜨리게 되었다. 왜 벌써 나를 다시 찾아오고 난리니 난 좀더 나중에 만나고 싶었는데

깊이 우선 탐색을 검색해보았다.

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.

트리, 그래프, 백트래킹, 스택 다 내가 모르는 영역이다. 정의부터 막히는데 이걸 공부하라고? 버겁다.

일단 트리와 그래프는 자료구조의 일종이라고 한다. 백트래킹은 모든 경우의 수를 전부 고려하는 알고리즘이라고 한다. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 백트래킹 알고리즘에 속한다고 한다. (최신 우선 탐색이라는 친구도 있다고 한다.) 아 일단 깊이 우선 탐색은 모든 경우의 수를 탐색하는 거구나. 그리고 재귀호출(함수가 스스로를 호출)을 사용하기 때문에 스택 오버플로우에 유의하라는 거구나.

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

이미지 출처 - https://aman.ai/code/dfs-vs-bfs/

이 그림을 보면 깊이 우선 탐색이 뭔지 직관적으로 느낄 수 있다. 오른쪽 트리의 초록색 선을 보면 1-2-4-7 첫번째 루트의 제일 깊은 곳까지 들어간 뒤 제일 최근 갈림길인 2로 돌아가 다른 갈래의 가장 깊은 지점인 5를 탐색한다. 그리고 그 이전 갈림길인 1로 돌아가 다른 갈래인 3-6-8을 탐색한다. 각 갈림길의 제일 깊은 지점까지 들어가며 탐색하여 깊이 우선 탐색이라고 부르는 것이다.

우선 최대한 간단한 구조의 트리로 구현해보며 이해해보기로 한다. 저 그림 속 예시와 똑같이 만들어볼까?

1. 노드 클래스 정의

아직 트리라는 자료구조를 공부해보지 못했지만 저 그림 생긴 걸 보니 나무처럼 생겨서 트리라고 부르는 것 같은데, 트리에서 각 자료에 해당하는 친구들을 노드(Node)라고 부르는 모양이다. 1, 2, 3, 4, ... 8이 각각 노드인 것이다.

class Node {
	let value: Int			// 값
    var neighbours: [Node]	// 이웃하는 노드들
    var visited: Bool		// 탐색 시 왔던 길인지 여부
    
    init(_ value: Int) {
    	self.value = value
        self.neighbours = []
        self.visited = false
    }
    
    func addNeighbour(_ node: Node) {
    	neighbours.append(node)
    }
}

2. 노드 추가

let node1 = Node(1)
let node2 = Node(2)
let node3 = Node(3)
let node4 = Node(4)
let node5 = Node(5)
let node6 = Node(6)
let node7 = Node(7)
let node8 = Node(8)

3. 이웃 노드 등록

node1.addNeighbour(node2) 	// 1 → 2

node2.addNeighbour(node4)	// 2 → 4
node2.addNeighbour(node5)	// 2 → 5

node4.addNeighbour(node7)	// 4 → 7

node1.addNeighbour(node3)	// 1 → 3
node3.addNeighbour(node6)	// 3 → 6
node6.addNeighbour(node8)	// 6 → 8

4. dfs 함수 정의

대망의 주인공 dfs 함수다. dfs를 처음 들었을 때 내가 모르는 어마어마한 미지의 개념이라고 느꼈던 것 대비 아주 간단하게 생겼다.

func dfs(node: Node) {
    node.visited = true
    
    print("visiting node: \(node.value)")
    
    for neighbour in node.neighbours {
        if !neighbour.visited {
            dfs(node: neighbour)
        }
    }
}

5. dfs 함수 호출

dfs(node: node1)

에게게 이게 끝이라고?

visiting node: 1
visiting node: 2
visiting node: 4
visiting node: 7
visiting node: 5
visiting node: 3
visiting node: 6
visiting node: 8

dfs(node: node1) 호출 결과 출력 내역이다. 정말 저 예시 그림 속 경로 그대로 출력되었다. 신기하다. 코드를 읽으며 이해해보자면 for문이 시작되는 순간 모든 이웃 노드를 방문하는 것은 정해져 있는 것이고, 방문하는 순간 visited를 true로 변경하여 두 번 방문하는 일이 없도록 하는 것이다.

드디어 dfs를 이해했으니, 이제 알고리즘 문제를 읽으러 가봐야겠다. 월요일에 내주신 문제를 수요일인 지금에서야 첫글자를 읽는다. 다음에는 너비 우선 탐색(bfs)에 대해 알아보겠다.