[알고리즘] 그래프 탐색 알고리즘 DFS & BFS

⭐ 자료구조란?

데이터를 효율적으로 접근하고 조작할 수 있게 데이터 구조를 만들어 관리하는 것을 뜻합니다.

선형 자료구조, 비선형 자료구조, 단순 자료구조, 파일 자료구조로 나뉘어집니다.

그 중에서 선형, 비선형 자료구조에 대해서 알아보겠습니다.

 

 

 

💡 선형 자료구조

 

● 배열(Array), 연결 리스트(Linked List), 큐(Queue), 스택(Stack) 등이 속합니다.

● 각 요소들이 일렬로 나열되어 있는 구조를 말합니다.

● 각 요소에 순차적으로 접근할 수 있습니다.

 

 

 

💡 비선형 자료구조

 

● 트리(Tree), 그래프(Graph), 힙(Heap) 등이 속합니다.

● 각 요소들이 계층적이거나, 연결 관계가 순차적으로 나열되지 않은 구조를 말합니다.

● 한 요소가 여러 요소와 연결될 수 있습니다.

 

 

⭐ DFS & BFS

선형 자료구조는 요소들을 차례대로 순회하면 되지만

비선형 자료구조는 선형 자료구조와 다르게 한 정점이 여러개의 정점들과 연결되어 있을 수 있으므로

연결된 정점들 중 어떤 정점을 먼저 탐색할지를 정해야합니다.

이와 같이 비선형 구조에서 탐색하는 대표적인 방식인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)에 대해서 알아보겠습니다.

 

 

 

DFS (깊이 우선 탐색)

---

● 하나의 경로를 완전히 탐색한 뒤 다음 경로로 넘어가는 방식

    ○ 쉽게 말해 탐색 방향을 정했으면 그 방향으로 꼼꼼하게 모두 탐색하고 돌아오는 방식

    ○ 이름처럼 깊게 탐색하는 방식

 

● 스택(Stack) 또는 재귀 함수를 사용해 구현

    ○ 재귀를 사용할 경우 재귀 호출이 너무 깊어지면 스택 오버 플로우 발생 위험이 있음

        ▶ 재귀의 깊이가 너무 깊어지지 않도록 문제의 범위를 제한

        ▶ 재귀 대신 반복문과 스택 방식을 고려

 

● 어디에 쓰일까?

    ○ 미로 찾기: 한 경로를 끝까지 탐색한 후 다른 경로를 시도하기 때문에 미로 탐색에 적합

    ○ 백트래킹 알고리즘 문제: 여러 백트래킹 알고리즘은 DFS 기반으로 구현

    ○ 강한 연결 요소 찾기: 그래프에서 강하게 연결된 컴포넌트를 찾을 때 적합

    ○ 퀘스트, 이벤트: 특정 퀘스트가 다른 퀘스트의 선행 조건인 경우 등의 구현에 사용

 

 

📘 DFS 탐색 순서

 

1. 방문한 노드를 저장하는 Visited와 탐색할 노드를 저장하는 Stack이 있습니다.

 

 

 

2. 0번 노드부터 탐색을 시작합니다. 

 

 

 

3. 0번 노드에 인접한 노드는 1, 2가 있습니다. 번호가 낮은 1번 노드로 탐색을 진행합니다.

 

 

 

4. 1번 노드에 인접한 노드는 5가 있습니다. 5번 노드로 탐색을 진행합니다.

 

 

 

5. 5번 노드에 인접한 노드가 더 이상 없습니다. 스택에서 5번 노드를 꺼냅니다.

 

 

 

6. 스택의 최상단에 위치한 1번 노드를 꺼냅니다. 탐색하지 않은 주변 노드가 있는지 확인합니다.

 

 

 

7. 스택의 최상단에 위치한 0번 노드를 꺼냅니다. 탐색하지 않은 노드인 2번 노드로 탐색을 진행합니다.

 

 

 

8. 2번 노드에 인접한 노드는 3이 있습니다. 3번 노드로 탐색을 진행합니다.

 

 

 

 

9. 3번 노드에 인접한 노드는 4가 있습니다. 4번 노드로 탐색을 진행합니다.

 

 

 

10. 4번 노드에 더 이상 인접한 노드가 없습니다. 스택의 최상단인 4번 노드를 꺼냅니다.

 

 

11. 스택에서 차례대로 노드를 꺼냅니다.

 

● 최종적인 탐색 순서는: 0 → 1 → 5 → 2 → 3 → 4

 

BFS (너비 우선 탐색)

---

● 모든 인접 노드를 먼저 탐색한 후, 그 다음 레벨로 이동하는 방식

    ○ 시작 노드에 인접한 노드 순으로 탐색하는 방식

    ○ 넓게 퍼져나가며 탐색하는 방식

 

● 큐를 사용해 구현

    ○ 인접 노드부터 탐색해야 하기 때문에 먼저 들어온 요소부터 탐색

 

● 어디에 쓰일까?

    ○ 최단 경로 탐색: 시작점에서 인접한 노드들부터 탐색하기 때문에 최단 경로 찾기에 적합

    ○ 네트워크 탐색: 네트워크나 소셜 네트워크에서 특정 사용자로부터 다른 사용자까지 도달하는 경로를 찾는데 활용

    ○ 범위 공격, 전염 효과: 게임 내에서 주변 적을 탐지 및 공격, 전염병 등의 효과가 점진적으로 퍼져나가는 효과 구현

 

 

📘 BFS 탐색 순서

 

1. 노드 0부터 탐색을 시작합니다.

 

 

 

2. 0번 노드에 인접한 노드 1, 2를 큐에 추가합니다.

 

 

 

3. 큐에서 1번 노드를 꺼내고 인접한 노드 5를 큐에 추가합니다.

 

 

 

4. 큐에서 노드 2번을 꺼내고 인접한 노드 3을 큐에 추가합니다.

 

 

 

5. 큐에서 노드 5번을 꺼냅니다. 더 이상 인접한 노드가 없으니 넘어갑니다.

 

 

 

6. 큐에서 노드 3번을 꺼냅니다. 인접한 노드 4번을 큐에 추가합니다.

 

 

 

7. 큐에서 노드 4번을 꺼냅니다.

 

 

 

8. 모든 노드를 방문했으므로 탐색을 종료합니다.

 

 

 

9. 최종적인 탐색 순서는: 0 → 1 → 2 → 5 → 3 → 4

 

 

 

DFS와 BFS 차이 정리

---

	DFS	BFS
탐색 방식	한 경로를 끝까지 내려간 뒤, 더 이상 갈 곳이 없어지면 되돌아와 다른 경로 탐색	시장 정점에서 가까운 노드부터 차례대로 탐색
자료구조	스택, 재귀함수	큐
최단 경로 보장	X (최단 거리를 고려하지 않음)	O (단, 비가중치 그래프에서 항상 최단 경로)
메모리 사용량	상대적으로 적음	레벨별 모든 노드를 저장해야 하기 때문에 큼
파생 탐색 알고리즘	백트래킹,	다익스트라 알고리즘, A*(에이스타) 알고리즘
주요 활용 사례	미로 생성, 백트래킹 문제	최단 경로 탐색, 주변 오브젝트 상호작용, 네트워크 거리 계산