240121_DFS, BFS

참조: https://www.youtube.com/watch?v=7C9RgOcvkvo
참조: https://www.youtube.com/watch?v=BsYbdUnKZ-Y
참조: https://veggie-garden.tistory.com/42
참조: https://iq.opengenus.org/dfs-vs-bfs/

DFS vs BFS

• DFS와 BFS 차이는 노드 방문 순서이다.

• 위의 표에서 효율성은 비슷하나, 거의 모든 경우에 DFS로 구현하는 것이 좀 더 표현이 쉽고 빠르다.
• 하지만 DFS는 항상 최적의 결과를 반환하는 것이 아니다. 따라서 목표에 이르는 경로가 복잡하다면 BFS를 써야 할 때도 있다.

---

DFS

깊이 우선 탐색(Depth First Search)

그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
스택 자료구조 또는 재귀함수를 사용해 그래프의 가장 깊은 곳까지 방문한 뒤, 다시 돌아가 다른 경로를 탐색한다.

• 동작 과정

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리. (이미 방문(탐색)했던 노드를 재방문하지 않기 위해)

  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문 처리. 만약 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.

  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복.

• 재귀 함수 사용 코드

import sys
input = sys.stdin.readline

N, M, V = map(int, input().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs_recursion(graph, start, visited):
    visited[start] = True

    for i in graph[start]:
        if not visited[i]:
            visited[i] = True
            dfs_recursion(graph, i, visited)

• 스택 사용 코드

import sys
input = sys.stdin.readline

N, M, V = map(int, input().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs_stack(graph, start, visited):
    stack = []
    stack.append(start)
    
    while stack:
        current = stack.pop()
        if not visited[current]:
            visited[current] = True
            stack.extend(reversed(graph[current]))

---

BFS

너비 우선 탐색(Breadth First Search)

인접 노드를 계속 큐에 넣어가며 큐에 들어온 순서대로 탐색을 시작

• 동작 과정

  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리.

  2. 큐에서 노드를 꺼내 해당 노드의 방문하지 않은 모든 인접 노드를 모두 쿠에 삽입하고 방문 처리.

  3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복.

• 관련 코드

import sys
from collections import deque
input = sys.stdin.readline

N, M, V = map(int, input().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
            
def bfs_queue(graph, start, visited):
    que = deque([start])
    que.append(start)
    
    while que:
        current = que.popleft()
        
        if not visited[current]:
            visited[current] = True
            que.extend(graph[current])