S533 BFS, DFS

BFS (Breadth First Search) : 너비 우선 탐색

 

BFS

1. 개념
   • 최대한 넓게 탐색하는 것
   • 큐의 개념이 사용된다.
   • 위 이미지를 참조하자면, s - 1 - 2 - 3 - 4 - 5 - 6 - 7 순서로 탐색한다.
2. 활용
   • 최단거리를 구하는 문제 
   • ex) 미로찾기 등
3. 장/단점
   
   • 장점
     • 무한히 깊은 경로여도 최단 경로를 반드시 찾을 수 있고 최단 경로 찾기에 적합하다.
     • 노드 수가 적고 깊이가 얕을 때 효과적으로 찾을 수 있다.
   • 단점
     • 큐를 이용하기 때문에 노드 수가 많아지면 메모리를 많이 소비한다.
     • 노드 수가 많아지면 탐색할 노드가 많아져 비효율적이다.
4. 코드 구현

# 첫번쨰 방법
def bfs_queue(start_node, bfs_graph):
    bfs_list = list()
    queue = list()
    queue.append(start_node)
    while queue:
        node = queue.pop(0)
        if node not in bfs_list:
            bfs_list.append(node)
            queue.extend(bfs_graph[node])
    return bfs_list

# 두번째 방법
def bfs_queue(start_node):
  bfs_list = [start_node]
  queue = [start_node]
  while queue:#외부반복문
    node = queue.pop(0)
    for i in bfs_graph[node]: #내부반복문 
      ##### 내부반복문에 대한 로직을 작성해보세요 #####
      if i not in bfs_list:
        bfs_list.append(i)
        queue.append(i)
  return bfs_list

 

DFS (Depth First Search): 깊이 우선 탐색

 

깊이 우선 탐색

1. 개념
   • 최대한 깊이 탐색하는 것
   • 스택의 개념이 사용된다.
   • 위 이미지를 참조하자면 1 - 2 - 4 - 5 - 3 순서로 탐색하게 된다.
   • (이는 1을 기준으로 탐색했을 때를 기준으로 DFS 했을 때이다.)
2. 활용
   • 경로의 특징을 저장해야 하는 문제
   • ex) 자동 미로 생성 (재밌는건 BFS는 미로 탐색을 잘 하고 DFS는 미로를 잘 만든다. 마치 경찰과 도둑, GAN의 descriminator 과 generator의 관계같다.)
3. 장/단점
   •  장점
     • BFS에 비해 저장 공간의 필요성이 적다.
     • 찾아야 하는 노드가 깊은데 좌측에 있을수록 BFS보다 유리하다.
   • 단점
     • 답이 아닌 경로가 매우 깊으면 그 경로에 빠진다. (= 노드가 무한할수록, 무한 루프에 빠진다.)
     • 찾은 해가 최단 경로라는 보장이 없다.
4. 코드 구현

def dfs_recur(node,dfs_graph ,dfs_list = []):
    dfs_list.append(node)
    for i in dfs_graph[node]:
        if i not in dfs_list:
            dfs_list = dfs_recur(i,dfs_graph,dfs_list)
    return dfs_list