[Algorithm] DFS와BFS

✔️DFS (깊이 우선 탐색)란?

DFS는 그래프나 트리에서 깊이를 우선으로 탐색하는 알고리즘이며, 한 지점에서 출발하여 그래프의 깊은 곳을 우선적으로 탐색하며 더 이상 진행할 수 없을 때 되돌아가 다음 경로를 탐색합니다.

💡 동작 방식

• 재귀 또는 스택을 사용하여 구현 가능합니다.
• 시작 노드를 방문하고, 이웃 노드 중 방문하지 않은 노드를 재귀적으로 방문합니다.
• 더 이상 방문할 이웃 노드가 없을 때, 이전 단계로 돌아가면서 다른 경로를 탐색합니다.

 

💡 사용 사례

• 미로 찾기, 그래프 순회, 트리 순회 등에 사용됩니다.
• 깊이 우선 탐색은 재귀 호출을 이용한 알고리즘에서 주로 사용됩니다.

 

💡 장단점

• 장점: 간단하고 구현이 쉽다. 더 깊은 경로를 먼저 탐색하여 빠르게 결과를 얻을 수 있을 때 효과적이다.
• 단점: 최단 경로를 보장하지 않으며, 무한 루프에 빠질 수 있다.

 

✔️BFS (너비 우선 탐색)란?

BFS는 그래프나 트리에서 너비를 우선으로 탐색하는 알고리즘이며, 한 지점에서 시작하여 해당 노드의 이웃 노드를 모두 방문한 후에 다음 레벨의 노드를 방문합니다.

💡 동작 방식

• 큐 (Queue)를 사용하여 구현합니다.
• 시작 노드를 큐에 넣고, 큐에서 노드를 하나씩 꺼내면서 이웃 노드를 큐에 추가합니다.
• 더 이상 방문할 노드가 없을 때까지 반복합니다.

 

💡 사용 사례

• 최단 경로 탐색, 네트워크 최단 거리 계산, 그래프 순회 등에 사용됩니다.
• 너비 우선 탐색은 큐를 사용하므로 최단 경로를 찾을 때 유용합니다.

 

💡 장단점

• 장점: 최단 경로를 보장하며, 무한 루프에 빠지지 않습니다.
• 단점: 구현이 다소 복잡하며, 깊이 우선 탐색보다 느릴 수 있습니다.