[Algorithm] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 알고리즘

🌵깊이 우선 탐색 DFS (Depth First Search) 란?

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

그 중 DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
즉, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 

 

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사
• 넓게(wide) 탐색하기 전에 깊게(deep) 탐색
• 모든 노드를 방문 하고자 하는 경우 사용
• 너비 우선 탐색(BFS)보다 간단하다
• 단순 검색 속도는 너비 우선 탐색(BFS)에 비해 느리다
• 자기 자신을 호출하는 순환 알고리즘 형태
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류

 

 

🌵깊이 우선 탐색 (DFS) 과정

DFS는 스택 자료구조(혹은 재귀함수)를 이용

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

 

다음과 같은 그래프가 주어졌을 경우,

 

1. 시작 노드는 1이며, 번호가 낮은 노드부터 탐색

2. 스택 최상단 노드 '노드 1'에 방문하지 않은 인접 노드 2,3,8 중 가장 낮은 숫자인 2를 스택에 넣고 방문처리

3. '노드 2'에서는 방문하지 않은 노드가 7뿐이기 때문에 7을 스택에 넣고 방문 처리

4. 스택 최상단 노드 '노드 7'에서는 방문하지 않은 인접 노드 6과 8중 낮은 숫자인 6을 스택에 넣고 방문 처리

 

 

5. 스택 최상단 노드 '노드 6'에는 방문하지 않은 인접 노드가 없으므로 다시 최상단 노드 7로 이동 후, 노드 8을 스택에 넣고 방문 처리

 

위의 과정을 방문하지 않은 노드가 없을 때까지 반복하면,

 

탐색 순서는 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 ->5 

 

 

 

🌵파이썬에서의 깊이 우선 탐색 (DFS) 구현

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

 

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],
    [2,3,8], # 1번 노드와 연결
    [1,7], # 2번 노드와 연결
    [1,4,5], # ...
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7] # 8번 노드와 연결
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

 

🚀결과

 

 

 

---

 

 

🌵너비 우선 탐색 BFS (Breadth First Search) 란?

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
즉, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 

 

• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것
•  두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택
• BFS는 재귀적으로 동작하지 않는다.
• 주의❗️그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다.
  이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용
• ‘Prim’, ‘Dijkstra’ 알고리즘과 유사

 

 

🌵너비 우선 탐색 (BFS) 과정

BFS는 큐 자료구조를 이용

 

깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

 

1. 시작 노드를 방문하고, 큐에 방문된 노드를 삽입(enqueue)한다.
    즉, 초기 상태의 큐에는 시작 노드만이 저장

 

-> 시작 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문

 

2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문
- 큐에서 꺼낸 노드를 방문
- 큐에서 커낸 노드과 인접한 노드들을 모두 방문
- 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue)
- 큐에 방문된 노드를 삽입(enqueue)

 

 

 

 

3. 큐가 소진될 때까지(= 큐가 빌 때까지 = 큐에서 더이상 꺼낼 노드가 없을 때까지) 반복

 

 

 

🌵파이썬에서의 너비 우선 탐색 (BFS) 구현

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
bfs(graph, 1, visited)

 

🚀결과

 

 

 

출처 : https://namu.wiki/w/BFS

 

 

 

🌵관련문제

🥈[백준 알고리즘 1260번 : DFS와 BFS ]

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

[SOLUTION]

https://gyurisinzorba.tistory.com/105?category=1019803 

[Python] 백준 알고리즘 1260번 : DFS와 BFS

---

 

 

 

 

---

~ 해당 포스팅은 업데이트 중 ~