인공지능 사관학교 - 2주차 (DFS, BFS / 깊이 우선 탐색, 너비 우선 탐색)

그래프

1. 정점 (Vertex)와 간선 (Edge)

• 정점: 그래프에서 데이터 항목을 나타내는 개체. 정점은 노드(node)라고도 불립니다.
• 간선: 정점 간의 관계를 나타내는 선. 간선은 링크(link) 또는 아크(arc)라고도 불립니다.

 

2. 예시 코드

 

 

3. 그래프의 종류

 

 

• 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프. 정점 A와 B가 연결되어 있으면 A에서 B로, B에서 A로 이동 가능합니다.
• 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프. 정점 A에서 B로 가는 경로가 있을 때, A에서 B로는 갈 수 있지만 B에서 A로는 갈 수 없는 경우가 있을 수 있습니다.
• 가중 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프. 가중치는 두 정점 간의 거리나 비용을 나타냅니다.

 

4. 인접 행렬 (Adjacency Matrix)와 인접 리스트 (Adjacency List)

• 인접 행렬: 정점 간의 연결을 2차원 배열로 표현. 정점 i와 j가 연결되어 있으면 matrix[i][j]는 1, 그렇지 않으면 0.

 

 

• 인접 리스트: 각 정점에 연결된 정점들의 리스트로 표현. 더 적은 메모리를 사용하며, 큰 그래프에서 유리합니다.

 

깊이 우선 탐색 / 너비 우선 탐색

 

 

깊이 우선 탐색 (DFS)

DFS는 그래프의 한 정점에서 시작하여 가능한 한 깊게 탐색한 후, 더 이상 갈 곳이 없으면 되돌아오는 방식으로 탐색을 진행합니다. 주로 스택을 사용하거나 재귀 호출을 통해 구현됩니다.

주요 특징

• 깊게 탐색 후, 막히면 백트래킹(되돌아가기)하는 방식.
• 모든 정점을 방문할 때까지 반복.

 

너비 우선 탐색

너비 우선 탐색 (BFS)

BFS는 그래프의 한 정점에서 시작하여 인접한 모든 정점을 먼저 탐색한 후, 그 다음 단계의 인접 정점을 탐색하는 방식으로 진행됩니다. 주로 큐를 사용하여 구현됩니다.

주요 특징

• 같은 레벨의 정점들을 모두 탐색한 후, 다음 레벨로 이동.
• 최단 경로를 찾는 데 유용.

구현

 

깊이 우선 탐색과 너비 우선 탐색의 비교

차이점

1. 탐색 방식
   • DFS: 깊게, 막힐 때까지 탐색한 후 되돌아오기.
   • BFS: 넓게, 같은 레벨의 모든 정점을 탐색한 후 다음 레벨로 이동.
2. 자료 구조
   • DFS: 스택(비재귀 구현) 또는 재귀 호출(내부적으로 스택 사용).
   • BFS: 큐.
3. 용도
   • DFS: 그래프의 모든 경로를 탐색하거나, 미로 찾기 등에서 사용.
   • BFS: 최단 경로를 찾는 문제에서 유용, 레벨 단위로 탐색.

요약

• DFS: 깊이 우선 탐색, 스택을 사용, 모든 경로 탐색에 유리.
• BFS: 너비 우선 탐색, 큐를 사용, 최단 경로 탐색에 유리.

팁

• 주로 코딩 테스트 / 알고리즘 문제들을 DFS가 많이 출제됨
• DFS가 동작 검증을 하는데 더 쉬워서 자주 사용됨
• 종종 어려운 문제들은 DFS가 아닌 BFS로 풀어야 시간 초과가 되지 않는 문제들도 존재

예제

DFS, 재귀 함수 - 파이썬 알고리즘 인터뷰 (p.324)

DFS, 스택 - 파이썬 알고리즘 인터뷰 (p.325)

 

 

BFS - 파이썬 알고리즘 인터뷰 (p.326)

 

 

이해하기 위한 나의 노력,,,,,