순회
그래프를 탐색하는 것을 말한다.
그래프는 Adjacency Matrix의 형태나 Adjacency List의 형태로 구현되며 순회 함수 호출 시 이 형태로 들어간다.
순회 방법으로는 대표적으로 BFS와 DFS가 있는데 둘 모두 무방향 그래프와 방향 그래프 모두 사용 가능하다.
다만 방향 그래프에서는 어떤 노드에서 시작하느냐에 따라서 모든 노드를 순회할 수 없는 경우의 수가 생길 수 있다.
BFS (너비 우선 탐색)
BFS는 너비 우선 탐색으로 시작 노드부터 시작하여 그 노드와 연결된 노드들을 차례대로 방문하는 방법이다.
Queue를 이용해서 구현할 수 있으며, 노드 N1로부터 노드 N2까지의 최단 경로를 알아내는데 주로 사용된다.
반복문을 이용한 BFS 문제 풀이 : 게임 맵 최단거리
DFS (깊이 우선 탐색)
DFS는 깊이 우선 탐색으로 시작 노드부터 한 방향으로 그래프의 끝까지 탐색했다가
그래프의 끝에 도달하면 되돌아와서 나머지 방향을 탐색하는 방식이다.
스택이나 재귀함수를 통해 구현하며 모든 경우를 탐색해봐야하는 브루트 포스 문제에 주로 사용된다.
재귀함수를 이용한 DFS 문제 풀이 : 일곱 난쟁이
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 순열(Permutation)의 코드화 (0) | 2023.04.05 |
|---|---|
| 조합(Combination)의 코드화 (0) | 2023.04.05 |
| DAG와 위상 정렬 (Topological Ordering) (0) | 2022.03.20 |
| Dynamic Programming(동적 계획법) (0) | 2022.03.16 |
| Recursion(재귀) (0) | 2022.02.24 |
