[DFS, BFS] 기본

1️⃣ DFS 

깊이 우선 탐색 방식

 

위와 같은 이미지의 그래프가 있을 때, DFS 방식은 

1-2-3-4-5-6-7-8-9-10-11-12로 노드를 탐색한다.

 

** 참고로 위의 그래프를 딕셔너리 형태로 나타내면 다음과 같다.

graph = { 1: [2, 7, 8],
    	  2: [3, 6],
          3: [4, 5],
          4: [],
          5: [],
          6: [], 
          7: [],
          8: [9, 12],
          9: [10],
          10: [],
          11: [],
          12: [] }

 

DFS의 sudo code를 파이썬으로 나타내면 다음과 같다.

def recursive_dfs(v, discoverd = []):
	discovered.append(v)  # 시작 노드를 discovered에 저장한 후 시작
    
    for w in graph[v]:  # v와 연결된 노드들을 탐색하며
    	if w not in discoverd:  # 이전에 조회한 노드가 아니면
        	discovered = recursive_dfs(v, discovered) # discovered에 추가시키고, 다음 노드로 깊이 탐색 & discovered update
            
    return discovered

2️⃣ BFS

넓이 우선 탐색 방식

위와 같은 이미지의 그래프가  있을 때, BFS 방식은

1-2-7-8-3-6-9-12-4-5-10-11로 노드를 탐색한다.

 

BFS의 sudo code를 파이썬으로 나타내면 다음과 같다.

def iterative_bfs(start_v):
	# discovered와 queue에 시작 노드 넣고 시작
	discovered = [start_v]
    queue = [start_v]
    
    while queue: # queue가 비기 전까지
    	v = queue.pop(0) # queue의 첫번째 요소 빼서 v에 저장. 처음엔 start_v가 v가 됨.
    	for w in graph[v]:
        	if w not in discovered: # 아직 조회되지 않은 노드라면
            	discovered.append(v) 
                queue.append(v)
                
    return discovered

 

3️⃣ 문제 풀이 시 DFS, BFS 선택 방법

둘 다 완전 탐색하는데 활용

대부분의 경우 DFS와 BFS 중 어느 것을 선택해도 무방한 문제들이 많다.

 

1) DFS or BFS 중 어느 것을 사용해도 무관한 경우

2) DFS를 사용하는 것이 압도적으로 편한 경우

3) BFS를 사용하는 것이 압도적으로 편한 경우

 

DFS	BFS
-  재귀적인 특징 -  백트래킹 -  모든 경우를 하나하나 전부 탐색하는 완전 탐색 문제 ex) 조합, 순열	-  깊이(depth)를 이용한 문제 ex) 최단경로, 미로탐색