[바킹독 알고리즘]0x0A강 - DFS

0x00 DFS

DFS( Depth First Search)

: 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

 

방문여부확인을 스택을이용한다

 

 

 

BFS( Breadth First Search)

: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

 

방문여부확인을 큐를이용한다

 

 

 

 

0x01 예시

 

 

 

 

0x02 BFS vs DFS

 

DFS는 한 방향으로 막힐때 까지 쭉 직진을 하는것처럼 보인다.

 

BFS, DFS 모두 순회하면서 체크하는 알고리즘이긴 하나 BFS에서 유용하게 썻던 "현재 보는 칸으로부터 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다"는 성질이 DFS에서는 성립하지 않는다. 그래서 거리를 계산할 때에는 DFS를 사용할 수 없다.

 

결국 앞으로 다차원 배열에서 순회하는 문제를 풀 때 계속 BFS만 짜게 된다.

 

앞으로 트리나 그래프 자료구조를 배울 때 DFS가 필요하다.