그래프탐색알고리즘

[Algorithm] DFS와 BFS

DFS와 BFS 란 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 탐색 알고리즘입니다. 이 두 알고리즘은 그래프의 노드를 탐색하는 방식에서 차이가 있습니다. DFS는 한 노드에서 시작하여 깊이를 우선으로 탐색하며, 해당 경로가 더 이상 진행할 수 없을 때 되돌아가서 다른 경로를 탐색합니다. 스택이나 재귀 함수를 사용하여 구현할 수 있습니다. DFS는 그래프의 깊은 부분을 우선적으로 탐색하므로, 해답이 깊은 단계에 위치한 경우 효율적일 수 있습니다. 하지만 무한 루프에 빠질 수 있으며, 최단 경로를 찾는 문제에서는 최적의 해를 보장하지 않을 수 있습니다. BFS는 한 노드에서 시작하여 인접한 모든 노드를 먼저 탐색한 후, 그 다음 레벨의 인접한 노드를 탐색합니다. 큐를 사용하여 구현할 수 있..