알고리즘 4주차 - BFS, DFS

BFS, DFS란?

BFS: 자료의 검색, 트리나 그래프를 탐색하는 방법으로써 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

DFS: 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더이상 방문하지 않은 정점이 없을때가지 방문하지 않은 모든 정점들에 대해서도 적용

이 두개가 필요한 이유: 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 탐색이 있는 반면 전부 탐색 해야하는 경우가 있다. 위 두 방법은 이때 모든 경우의 수를 탐색할 때 필요한 알고리즘이다.

💡

DFS 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구합니다. 따라서 공간을 적게 씁니다. 그러나 최단 경로를 탐색하기 쉽지 않습니다. BFS 는 최단 경로를 쉽게 찾을 수 있습니다! 모든 분기되는 수를 다 보고 올 수 있으니까요. 그러나, 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고, 모든 걸 다 보고 오다보니 시간이 더 오래걸릴 수 있습니다. # 출처: 스파르타 코딩클럽

DFS 구현

• 재귀함수

💡

- 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. - 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. - 만약 끝에 도달했다면 리턴한다. 1. 루트 노드부터 시작한다. 2. 현재 방문한 노드를 visited 에 추가한다. 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다. 4. 2부터 반복한다.

# 코드 스니펫
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []


def dfs_recursion(adjacent_graph, cur_node, visited_array):
    # 구현해보세요!
    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []


def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph:
        if adjacent_node not in visited_array:
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)
    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

• 스택

재귀함수를 통해서는 무한정 깊어지는 노드가 있는 경우 에러가 발생할 수 있음. RecursionError

DFS는 탐색하는 원소를 최대한 깊게 따라가야 한다. 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드를 저장해두고 가장 마지막에 넣은 노드들만 꺼내서 탐색하면 되는 것이다.

스택을 이용하면 DFS를 재귀 없이 구현할 수 있다.

방문한 것은 visited, 방문하지 않은 것은 스택에 추가하면서 구현 가능하다.

💡

1. 루트 노드를 스택에 넣습니다. 2. 현재 스택의 노드를 빼서 visited 에 추가한다. 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다. 4. 2부터 반복한다. 5. 스택이 비면 탐색을 종료한다. # 출처: 스파르타코딩클럽

스택에 추가하기에 스택에 추가된 가장 마지막(Last in First out) 노드를 먼저 빼서 탐색한다.

인접한 노드들이 이미 방문한 것이면 스택에 추가하지 않음.

재귀랑 구현한 방식과는 탐색 순서가 다름

# 코드 스니펫
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}


def dfs_stack(adjacent_graph, start_node):
    # 구현해보세요!
    return


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}


def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []

    while stack:
        current_node = stack.pop()
        visited.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

BFS 구현

BFS는 현재 인접한 노드 먼저 방문해야 한다. 인접한 노드 중 방문하지 않은 노드들을 저장해두고 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.

즉 큐 를 이용하면 BFS를 구현 가능하다.

💡

1. 루트 노드를 큐에 넣습니다. 2. 현재 큐의 노드를 빼서 visited 에 추가한다. 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다. 4. 2부터 반복한다. 5. 큐가딕 비면 탐색을 종료한다.

DFS와 비슷하다. 단지 스택이 아닌 큐를 쓴다는 점이 다르다!(First in First out)

인접한 노드를 큐에 저장하면서 가장 앞에있는 것부터 탐색 시작!

# 코드 스니펫
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    # 구현해보세요!
    return


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    queue = [start_node]
    visited = []
    while queue:
        current_node = queue.pop(0)
        visited.append(current_node)
        for adj_node in adj_graph[current_node]:
            if adj_node not in visited:
                queue.append(adj_node)
    return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!