[Swift] DFS/BFS란 무엇인가? - 깊이우선탐색과 너비우선탐색 구현

작성일 : 2023-04-06

DFS/BFS란 ?

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘입니다. 이 알고리즘들은 그래프에서 노드 간의 경로를 찾거나, 연결된 구성 요소를 찾는 등 다양한 그래프 문제를 해결하는 데 사용됩니다.

DFS는 깊이 우선 탐색 알고리즘이며, 스택이나 재귀 함수를 사용하여 구현됩니다. 이 알고리즘은 한 경로를 따라 끝까지 탐색한 후, 다음 경로를 찾습니다. 즉, 한 노드에서 출발하여 가능한 한 멀리까지 탐색한 후, 다시 돌아와 다음 경로를 탐색합니다. DFS는 그래프의 구성 요소, 사이클, 위상 정렬 등을 찾는 데 유용합니다.

BFS는 너비 우선 탐색 알고리즘이며, 큐를 사용하여 구현됩니다. 이 알고리즘은 한 노드에서 시작하여 인접한 노드를 모두 방문한 후, 이어지는 모든 노드를 탐색합니다. 즉, BFS는 노드의 깊이가 낮은 것부터 탐색하며, 최단 경로 문제를 해결하는 데 사용됩니다.

DFS와 BFS는 둘 다 그래프 탐색에 사용되지만, DFS는 한 경로를 따라 탐색하며, BFS는 모든 인접한 노드를 탐색합니다. 이러한 차이점은 DFS와 BFS를 사용할 때 해결하려는 문제에 따라 선택해야 합니다.

Swift 코드로 DFS 구현


swift
func dfs(_ graph: [[Int]], _ startNode: Int, _ visited: inout [Bool]){
    visited[startNode] = true
    print(startNode, terminator: " ")

    for nextNode in graph[startNode] {
        if !visited[nextNode] {
            dfs(graph, nextNode, &visited)
        }
    }
}

위 함수는 그래프의 인접 리스트와 시작 노드를 인자로 받아, DFS를 수행하고 방문한 노드를 출력합니다. 방문한 노드를 출력하는 부분을 수정하여 원하는 출력 형태로 변경할 수 있습니다. 위의 코드를 보면 popLast를 사용하여 stack 구조를 구현한 것을 확인할 수 있습니다. 일반적으로 실 사용시 위 코드를 아래와 같이 재귀적으로 호출하여 문제를 해결합니다.


swift
let graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

var visited = [Bool](repeating: false, count: graph.count)

dfs(graph, 1, &visited)

Swift 코드로 BFS 구현

아래 함수는 그래프의 인접 리스트와 시작 노드를 인자로 받아, BFS를 수행하고 방문한 노드를 출력합니다.


swift
func bfs(_ graph: [[Int]], _ startNode: Int, _ visited: inout [Bool]){
    var visited = [Bool](repeating: false, count: graph.count)
    var queue = [Int]()
    queue.append(startNode)

    while !queue.isEmpty {
        let node = queue.removeFirst()
        if !visited[node] {
            print(node, terminator: " ")
            visited[node] = true
            for neighbor in graph[node] {
                queue.append(neighbor)
            }
        }
    }
}

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

var visited = [Bool](repeating: false, count: graph.count)

dfs(graph, 1, &visited)

DFS 대표 문제

사이클 찾기: DFS는 그래프에서 사이클을 찾는 데 사용됩니다. 한 노드에서 출발하여 다음 노드로 이동할 때마다 방문 여부를 검사하고, 이미 방문한 노드를 만나면 사이클이 존재한다는 것을 알 수 있습니다.
미로 찾기: DFS는 미로 찾기 문제를 해결하는 데 사용됩니다. 미로를 그래프로 모델링하고, 시작점에서 출발하여 목적지에 도달할 때까지 DFS를 반복하여 경로를 찾습니다.
위상 정렬: DFS는 방향 그래프에서 위상 정렬을 수행하는 데 사용됩니다. DFS를 수행하면서 더 이상 방문할 수 없는 노드부터 역순으로 정렬하여 위상 정렬을 수행할 수 있습니다.
연결 요소 찾기: DFS는 그래프에서 연결 요소를 찾는 데 사용됩니다. DFS를 수행하면서 방문한 노드들을 하나의 연결 요소로 묶을 수 있습니다.

BFS 대표 문제

네트워크 통신: BFS는 컴퓨터 네트워크에서 노드 간의 통신을 모델링하는 데 사용됩니다. 노드 간의 연결을 그래프로 모델링하고, BFS를 수행하여 각 노드가 통신할 수 있는 노드를 찾을 수 있습니다.
최단거리 찾기 문제: 미로 탐색 문제는 DFS로도 해결할 수 있습니다. 하지만, BFS와는 다르게 깊이 우선 탐색이기에 BFS에 배해 비효율적이고 시험에서 시간 초과가 발생할 수 있습니다. 따라서 BFS를 이용하여 문제를 해결하는게 최선입니다.
퍼즐 해결: BFS는 퍼즐을 해결하는 데 사용됩니다. 예를 들어, 8-퍼즐과 같은 퍼즐은 그래프로 모델링할 수 있으며, BFS를 사용하여 퍼즐을 해결할 수 있습니다.
상태 공간 탐색: BFS는 상태 공간 탐색에 사용됩니다. 상태 공간은 가능한 상태의 모음을 말하며, 각 상태는 그래프의 노드로 모델링됩니다. BFS를 사용하여 시작 상태에서 목적 상태로 이동할 수 있는 모든 경로를 찾을 수 있습니다.
컴파일러 최적화: BFS는 컴파일러에서 코드 최적화를 수행하는 데 사용됩니다. 컴파일러는 소스 코드를 그래프로 모델링하고, BFS를 사용하여 코드 최적화를 수행합니다.

[Swift] DFS/BFS란 무엇인가? - 깊이우선탐색과 너비우선탐색 구현

[Swift] DFS/BFS란 무엇인가? - 깊이우선탐색과 너비우선탐색 구현

DFS/BFS란 ?

Swift 코드로 DFS 구현

Swift 코드로 BFS 구현

DFS 대표 문제

BFS 대표 문제

참고 자료