DFS는 깊이 우선 탐색 알고리즘으로, 스택이나 재귀 호출을 이용하여 구현할 수 있다.
시작 노드에서부터 한 경로를 따라 최대한 깊게 탐색한 후, 다른 경로를 탐색한다.
이러한 방식으로 탐색을 진행하면서 방문한 노드를 스택에 저장하고, 더이상 탐색할 수 없을 때 스택에서 노드를 꺼내어 역순으로 출력한다. DFS는 그래프의 구조를 파악하는데 유용하며, 미로 찾기 등의 문제를 해결하는데 활용된다.
DFS를 이용하여 그래프를 탐색할 때는, 방문한 노드를 기록해야 한다. 이를 위해 visited 리스트를 만들어서 방문한 노드를 저장한다. DFS에서는 스택 또는 재귀 함수를 이용하여 노드를 방문하게 된다. 스택이나 재귀 함수가 호출될 때마다, 해당 노드와 연결된 인접 노드 중에서 방문하지 않은 노드를 스택에 저장하고, 그 노드를 방문한다. 이러한 과정을 반복하여 그래프를 탐색하게 된다.
BFS는 너비 우선 탐색 알고리즘으로, 큐를 이용하여 구현할 수 있다.
BFS는 시작 노드에서부터 인접한 노드를 모두 탐색한 후, 다음 노드로 이동한다. 이러한 방식으로 탐색을 진행하면서 방문한 노드를 큐에 저장하고, 먼저 저장된 노드부터 출력한다. BFS는 최단 경로를 찾거나, 노드 간 최단 거리 등을 구하는데 활용된다.
BFS를 이용하여 그래프를 탐색할 때는, 방문한 노드를 기록하고, 인접한 노드를 큐에 저장한다. 큐에서 노드를 꺼낸 후, 해당 노드와 연결된 인접 노드 중에서 방문하지 않은 노드를 큐에 추가한다. 이러한 과정을 반복하여 그래프를 탐색하게 된다.
'코딩테스트 공부' 카테고리의 다른 글
| 자바스크립트의 9가지 코드 트릭 (0) | 2022.11.01 |
|---|---|
| 시간복잡도 (0) | 2022.11.01 |
| 자료구조의 종류 (0) | 2022.11.01 |