BFS와 DFS

 

순회

 

그래프를 탐색하는 것을 말한다.

그래프는 Adjacency Matrix의 형태나 Adjacency List의 형태로 구현되며 순회 함수 호출 시 이 형태로 들어간다.

순회 방법으로는 대표적으로 BFS와 DFS가 있는데 둘 모두 무방향 그래프와 방향 그래프 모두 사용 가능하다.

다만 방향 그래프에서는 어떤 노드에서 시작하느냐에 따라서 모든 노드를 순회할 수 없는 경우의 수가 생길 수 있다.

BFS (너비 우선 탐색)

 

 

BFS는 너비 우선 탐색으로 시작 노드부터 시작하여 그 노드와 연결된 노드들을 차례대로 방문하는 방법이다.

Queue를 이용해서 구현할 수 있으며, 노드 N1로부터 노드 N2까지의 최단 경로를 알아내는데 주로 사용된다.

 

반복문을 이용한 BFS 문제 풀이 : 게임 맵 최단거리

DFS (깊이 우선 탐색)

 

 

DFS는 깊이 우선 탐색으로 시작 노드부터 한 방향으로 그래프의 끝까지 탐색했다가

그래프의 끝에 도달하면 되돌아와서 나머지 방향을 탐색하는 방식이다.

스택이나 재귀함수를 통해 구현하며 모든 경우를 탐색해봐야하는 브루트 포스 문제에 주로 사용된다.

 

재귀함수를 이용한 DFS 문제 풀이 : 일곱 난쟁이