DFS 와 BFS 구현원리 & 코드

안녕하세요! daily_D 입니다! 👩🏻‍💻
오늘은 DFS 와 BFS의 원리와 이를 코드로 작성하는 방법에 대해서 써볼까합니다!

DFS 와 BFS, 알고리즘하면 거의 가장 먼저 배우게 되는 것들이죠! 
아마 알고리즘 원리는 몰라도 이름은 들어보신 분들이 많을거에요!
그래서 DFS, BFS 가 뭐냐! 하면!!

DFS는 Depth-First-Search의 약어로 깊이 우선 탐색이고
BFS 는 Breadth-First-Search 의 약어로 너비 우선 탐색입니다.

이 둘은 그래프를 탐색하는 방법들입니다!
그럼 그래프가 뭐냐.. 하면

그래프는 정점(node)들과 이 정점들을 연결하는 간선(edge)으로 이루어진 자료구조를 말합니다.
그래프 탐색은 하나의 정점을 시작으로 다른 정점들을 모두 한번씩 방문하는 것을 말하고 DFS와 BFS 는 그 방법들 중 가장 대표적인 두개입니다. 

1. 입력값 저장

우선, DFS, BFS 를 구현하기 위해서는 입력값을 queue 에 저장하는 단계가 필요합니다.
만약 아래의 경우로 입력값이 들어온다면

1 2 1 3 1 4 2 4 3 4

순서대로 queue[a].push(b) & queue[b].push(a) 과정을 거쳐 아래와 같은 queue를 만들수 있습니다.

반면, 아래의 경우로 입력값이 들어온다면

5 4 5 2 1 2 3 4 3 1

순서대로 queue[a].push(b) & queue[b].push(a) 과정을 수행한 후 정렬을 해야 아래의 dfs, bfs 원리를 적용할 수 있습니다.

2. DFS & BFS 원리

아래의 그래프에서 **탐색을 시작할 정점의 번호를 1 이라고 가정하고 DFS, BFS 를 그림으로 설명하겠습니다.**

1. 깊이 우선 탐색 (DFS, Depth-First Search)**:** 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
일반적으로 DFS 는 스택 또는 재귀함수로 구현합니다.

2. 너비 우선 탐색 (BFS, Breadth-First Search)**: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동**
일반적으로 BFS 는 큐로 구현합니다

위의 그림을 코드로 나타낸 코드는 아래와 같습니다.

DFS

def dfs(start):
    visited[start] = 1
    route.append(start)
    for i in arr[start]:
        if visited[i] == 0:
            dfs(i)


route = []
arr = [[], [2, 3, 4],[1, 4],[1, 4],[1, 2, 3]]
visited = [0, 0, 0, 0, 0]
dfs(1)
print(route)

// 1, 2, 4 ,3

BFS

def bfs(start):
    route = [start]
    visited[start] = 1
    next = []
    while visited.count(1) < N:
    print(next)
    for i in arr[start]:
        next.append(i)
    for n in next:
        if visited[n] == 0:
            visited[n] = 1 
            route.append(n)


route = []
arr = [[], [2, 3, 4],[1, 4],[1, 4],[1, 2, 3]]
visited = [0, 0, 0, 0, 0]
bfs(1)
print(route)

// 1, 2, 3, 4