[알고리즘] dfs와 bfs

dfs는 깊이 우선 탐색으로 자식노드부터 탐색하는 기법이고,

bfs는 넓이 우선 탐색으로 형제노드들부터 탐색하는 기법이다.

dfs를 구현하는 방법으로는 스택을 사용하는 방법과 재귀를 사용하는 방법이 있고, bfs를 구현하는 방법은 큐 혹은 데크를 사용하는 방법이 있다.

 

dfs를 구현할 때에는 이미 방문한 노드 정보를 저장하는 visit과 앞으로 찾아가야할 노드를 기준으로 데이터를 탐색한다.

이미 방문을 했다면 무시하고, 방문하지 않았다면 탐색한다. 

그럼 우선 dfs 구현 방법을 살펴보자.

 

---

1. 스택 활용 방법

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

스택에는 시작 노드부터 순차적으로 자식노드들과 그 자식노드들의 자식노드들이 쌓인다.

따라서 스택의 위에서부터 아래로 level이 깊은 노드들이 쌓여있다. 

 

스택을 사용하는 이유는, dfs는 자식노드를 우선  탐색하므로, 가장 위에 있는 것에 대해 먼저 탐색하므로 pop한 노드를 탐색해주면 되기 때문이다.

반대로 생각하면 bfs는 형제 노드를 우선 탐색하므로 pop(0)한 노드를 우선 탐색해야 하므로, 큐보다는 데크를 사용하는 것이 더 효율적이다.

---

2. 재귀 활용 방법

def dfs(graph,start_node,visit):
    #방문 기록에 start_node 추가
    visit.append(start_node)
    #start_node의 자식 노드들에 대해서
    for node in graph[start_node]:
        #해당 자식 노드를 처음 방문 한다면
        if node not in visit:
            #해당 자식 노드의 자식 노드들에 대해 탐색한다.
            dfs(graph,node,visit)
    return visit

---

이번엔 bfs 코드이다. dfs에서 popleft()를 사용한다는 점을 제외하고는 동일하다.

def bfs(graph,start_node):
    visit = []
    q =deque([])
    #큐에 첫 시작 노드를 넣는다.
    q.append(start_node)
    #q에 원소가 있는 동안에
    while q:
        #큐의 첫번째 원소를 뽑아온다.
        node = q.popleft()
        #뽑아온 노드를 처음 방문한다면
        if node not in visit:
            #방문 기록에 해당 노드를 추가한다. 
            visit.append(node)
            # 자식 노드들을 큐에 넣는다. 
            # 위에서 큐에서 popleft를 하므로, 방금 추가한 자식 노드들은 나중에 고려되고,
            # q의 앞부분은 node의 형제노드들이 있으므로 node의 형제 노드를 먼저 고려한다. 
            q.extend(graph[node])
    return visit

---

백준에서 dfs와 bfs를 사용하는 문제풀이들을 살펴보자.

 

1. #1012 유기농 배추

https://live-for-myself.tistory.com/212

[CodingTest] 백준 python #1012 유기농 배추