자료구조 4주차 _ DFS & BFS

자료구조 4주차 _ DFS & BFS

---

📌 DFS란? 

Dep First Search

DFS, [출처 : 스파르타 코딩클럽]

인접한 노드를 끝까지 탐색

끝까지 파고드는 것이라, 그래프 최대 깊이 만큼의 공간을 요구

공간↓ 최단 경로 탐색 어려움

 

📌 BFS란?

Breadth First Search

BFS [출처 : 스파르타 코딩클럽]

한 노드를 시작으로 인접한 모든 정점들을 다 둘러보는 방식

모든 분기되는 수를 다 저장함.

공간↑ 최단 경로 쉽게 찾을 수 있음

 

모든 경우의 수를 다 탐색해야하는 경우가 있음.

---

📌 DFS 재귀함수 구현해보기

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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 = []

# 1. 시작 노드(루트 노드)인 1부터 탐색합니다.
# 2. 현재 방문한 노드를 visited_array 에 추가합니다.
# 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문합니다.
# visited_array = [1]
def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph[cur_node]:
        # print(adjacent_node)
        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] 이 출력되어야 합니다!

1에서 인접한 2를 방문 visited_array 에 [1,2]

2에서 인접한 1,3 중에 방문한 적 없는 3 방문 visited_array [1,2,3]

3에서 인접한 2,4 중에 방문한 적 없는 4 방문 visited_array [1,2,3,4]

...

 

방문 한적 있는지, 없는지 확인하는 if문 자체가 탈출 조건임!

없으면 재귀함수로 가지 않을 것이기 때문!

---

📌 DFS 스택 구현해보기

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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]
}

# 1. 시작 노드를 스택에 넣습니다.
# 2. 현재 스택의 노드를 빼서 visited에 추가합니다.
# 3. 현재 방문한 노드와 인접한 노드 중에서 방문하지 않은 노드를 스택에 추가합니다.

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] 이 출력되어야 합니다!

stack -> [] visited -> [1]

 

1과 인접한 2,5,9를 스택에 넣어주고 하나씩(스택의 제이 마지막 자리) 탐색!

stack -> [2, 5, 9] visited -> [1]

stack -> [2, 5] visited -> [1, 9]

 

9와 가장 인접한 1,10중에 탐색한적 없는 10을 스택에 넣어주고 탐색~

stack -> [2, 5, 10] visited -> [1, 9]

stack -> [2, 5] visited -> [1, 9, 10]

...

 

탐색 순서는 다르지만, 깊이 우선으로 탐색한다는 점은 동일!

---

📌 BFS 큐로 구현해보기

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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]
}

# 1. 시작 노드를 큐에 넣습니다.
# 2. 현재 큐의 노드를 빼서 visited에 추가합니다.
# 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

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] 이 출력되어야 합니다!

queue -> [] visited -> [1]

 

1와 인접한 노드 2,3,4를 큐에 넣고 큐의 맨앞부터 방문

queue ->[2, 3, 4] visited -> [1]

queue -> [3, 4] visited -> [1, 2]

 

2와 인접한 노드 1,5를 큐에 넣고 큐의 맨앞부터 방문

queue -> [3, 4, 5] visited -> [1, 2]

queue -> [4, 5] visited -> [1, 2, 3]

...