[패스트캠퍼스 :: 코딩테스트 인강] 9주차 ① 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

그래프 기본 탐색 알고리즘 - 01. 너비 우선 탐색(BFS) - 1

그래프 기본 탐색 알고리즘 - 02. 너비 우선 탐색(BFS) - 2

그래프 기본 탐색 알고리즘 - 03. 너비 우선 탐색(BFS) - 3

그래프 기본 탐색 알고리즘 - 04. 깊이 우선 탐색(DFS) 

 

---

 

 

 

 

 BFS와 DFS 란?

• 대표적인 그래프 탐색 알고리즘
  • 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
  • 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

 

 

BFS/DFS 방식 이해를 위한 예제

• BFS 방식: A - B - C - D - G - H - I - E - F - J
  • 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함
• DFS 방식: A - B - D - E - F - C - G - H - I - J
  • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

 

 

 

 

BFS 알고리즘 구현

• 자료구조 큐를 활용함
  • need_visit 큐와 visited 큐, 두 개의 큐를 생성

 

 

 

 

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

 

 

시간 복잡도

• 일반적인 BFS 시간 복잡도
  • 노드 수: V
  • 간선 수: E
    • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
  • 시간 복잡도: O(V + E)

 

 

 

DFS 알고리즘 구현

• 자료구조 스택과 큐를 활용함
  • need_visit 스택과 visited 큐, 두 개의 자료 구조를 생성

BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS는 스택과 큐를 활용한다는 차이가 있음을 인지해야 함

• 큐와 스택 구현은 별도 라이브러리를 활용할 수도 있지만, 간단히 파이썬 리스트를 활용할 수도 있음

 

 

 

 

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

 

시간 복잡도

• 일반적인 DFS 시간 복잡도
  • 노드 수: V
  • 간선 수: E
    • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
  • 시간 복잡도: O(V + E)

 

 

 

---

 

 

개인적으로 코딩 테스트 문제 중에 제일 응용하기 힘든 알고리즘인 것 같다.

하지만 관련 문제가 가장 많이 출제되는 것 같으니 열심히 하는 걸로....

 

 

코딩 못 참지

 

 

 

 

 

 

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스