[알고리즘] DFS, BFS

Judy·2023년 3월 8일

알고리즘

목록 보기

5/6

DFS

깊이 우선 탐색 (Depth First Search)
깊이(자식 노드)를 우선적으로 탐색하는 방법

장단점

장점

현 경로 상의 노드만 기억하면 되므로 저장공간 수요가 적다
목표 노드가 깊은 단계에 있을 경우 빠르게 구할 수 있다

단점

목표 노드가 없는 경로에 깊이 빠질 가능성이 있다
최단 경로로 찾는다는 보장이 없다
트리의 깊이가 목표 노드 깊이가 같을 때 최악의 경우 모든 노드를 다 검사하게 된다

예시 코드

위와 같은 그래프일 때,

let graph = [[1, 2],
             [0, 3, 4],
             [0],
             [1, 5, 6],
             [1],
             [3],
             [3]
]

var isVisited = Array(repeating: false, count: graph.count) // 방문한 노드인지 확인하는 배열

func depthFirstSearch(start: Int) -> [Int] {
    var searchList: [Int] = []
    var needVisitStack = [start]	// 전달받은 start 노드부터 시작
    
    while !needVisitStack.isEmpty  {
        let node = needVisitStack.removeLast() // 방문할 노드에서 하나 꺼내기
        if isVisited[node] { continue } // 이미 방문한 노드이면 지나가기
        
        isVisited[node] = true	// 방문함으로 표시
        searchList.append(node)
        graph[node].forEach {
            needVisitStack.append($0)	// 인접한 노드를 방문할 노드 리스트에 넣기
        }
    }
    
    return searchList
}

아래와 같이 재귀함수를 사용하는 방법도 있다.

func depthFirstSearch(start: Int) {
    isVisited[start] = true
    
    graph[start].forEach {
        if isVisited[$0] != true {
            isVisited[$0] = true
            print($0)
            depthFirstSearch(start: $0)
        }
    }
}

BFS

너비 우선 탐색 (Breadth First Search)
인접한 노드(형제 노드)를 우선적으로 탐색하는 방법

장단점

장점

목표 노드까지 최단 경로를 보장한다

단점

경로가 매우 길 경우 탐색 가지가 증가하여 많은 저장 공간이 필요하다
해가 존재하지 않는 유한 그래프에서는 모든 그래프를 탐색한 후 실패한다
무한 그래프의 경우 찾지도 못하고, 끝내지도 못한다

예시 코드

func breadthFirstSearch(start: Int) -> [Int] {
    var serchList: [Int] = [start]	// 방문한 노드를 담는 배열
    let queue = Queue<Int>()	// 방문할 노드를 담는 큐
    queue.enqueue(start)
    
    while !queue.isEmpty {	// 방문할 노드가 없을 때까지 반복
        guard let node = queue.dequeue() else { return [] }
        isVisited[node] = true	// 방문 표시로 변경
        
        graph[node].forEach {
            if isVisited[$0] != true {
                queue.enqueue($0)	// 인접한 노드를 방문할 큐에 넣고
                serchList.append($0)
                isVisited[$0] = true // 바로 방문
            }
        }
    }
    
    return serchList
}