그래프 탐색 알고리즘은 컴퓨터 과학에서 가장 기본적이면서도 강력한 도구입니다. 특히 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 다양한 문제 해결에 활용되는 필수적인 알고리즘입니다.
BFS(너비 우선 탐색)에 대해
BFS는 그래프나 트리 구조에서 시작 노드로부터 가까운 노드부터 차례대로 탐색하는 알고리즘입니다. 마치 물결이 퍼져나가듯이, 시작점에서 가까운 노드부터 방문하고 점점 멀리 있는 노드로 확장해 나가는 방식으로 동작합니다.
작동 원리
BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. 기본적인 작동 과정은 다음과 같습니다:
- 시작 노드를 큐에 넣고 '방문 완료'로 표시합니다.
- 큐가 빌 때까지 다음 과정을 반복합니다:
- 큐에서 노드를 하나 꺼냅니다.
- 해당 노드의 모든 인접 노드 중 아직 방문하지 않은 노드를 모두 큐에 넣고 '방문 완료'로 표시합니다.
이러한 방식으로 BFS는 시작 노드로부터의 거리가 가까운 순서대로 노드를 탐색합니다.
BFS의 특징
- 최단 경로 찾기: 가중치가 없는 그래프에서 두 노드 간의 최단 경로를 찾는 데 이상적입니다.
- 레벨 순회: 트리에서 각 레벨의 노드를 순차적으로 방문할 때 사용됩니다.
- 연결 컴포넌트 찾기: 그래프의 연결된 구성 요소를 식별하는 데 유용합니다.
- 공간 복잡도: 최악의 경우 O(V)의 공간이 필요합니다(V는 노드의 수).
- 시간 복잡도: 인접 리스트 표현에서 O(V+E), 인접 행렬 표현에서 O(V²)의 시간이 소요됩니다(E는 간선의 수).
구현 예시
BFS를 파이썬으로 구현한 간단한 예시입니다. graph에는 이전 포스팅에서 만든 인접리스트를, start는 처음 시작점을 넣으면 됩니다. 다양한 경우에 쓰이지만 대표적으로는 최단 경로 탐색이 있습니다.
DFS(깊이 우선 탐색)에 대해
DFS는 그래프나 트리 구조에서 가능한 한 깊이 들어가면서 탐색하는 알고리즘입니다. 미로를 탐색할 때 한 방향으로 끝까지 진행하다가 더 이상 나아갈 수 없으면 되돌아와 다른 방향을 탐색하는 방식과 유사합니다.
작동 원리
DFS는 스택(Stack) 자료구조나 재귀 함수를 통해 구현됩니다. 기본적인 작동 과정은 다음과 같습니다:
- 시작 노드를 스택에 넣고 '방문 완료'로 표시합니다.
- 스택이 빌 때까지 다음 과정을 반복합니다:
- 스택에서 노드를 하나 꺼냅니다.
- 해당 노드를 처리합니다(출력 등).
- 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 스택에 넣고 '방문 완료'로 표시합니다.
재귀적 접근 방식에서는 각 노드를 방문할 때마다 그 노드의 모든 인접 노드에 대해 재귀적으로 DFS 함수를 호출합니다.
DFS의 특징
- 경로 찾기: 두 노드 사이의 경로가 존재하는지 확인하는 데 유용합니다.
- 사이클 감지: 그래프 내의 사이클을 감지하는 데 사용됩니다.
- 위상 정렬: 방향성 비순환 그래프(DAG)에서 노드의 선형 순서를 찾는 데 활용됩니다.
- 연결 컴포넌트: 그래프의 연결된 컴포넌트를 식별하는 데 사용됩니다.
- 공간 복잡도: 최악의 경우 O(H)의 공간이 필요합니다(H는 그래프의 높이 또는 최대 깊이).
- 시간 복잡도: 인접 리스트 표현에서 O(V+E), 인접 행렬 표현에서 O(V²)의 시간이 소요됩니다.
구현 예시
DFS를 파이썬으로 구현한 예시입니다. 재귀적 방법으로 구현한 것입니다. 대부분의 DFS는 재귀적으로 구현됩니다.
이것으로 할 수 있는 것들
BFS와 DFS는 코딩 테스트에서 자주 출제되는 핵심 알고리즘입니다. 각각의 알고리즘이 코딩 테스트에서 어떻게 활용되는지 알아보겠습니다.
BFS로 해결하기 좋은 코딩 테스트 문제
- 최단 경로 찾기 문제
- 미로에서 출발점에서 도착점까지의 최소 이동 횟수
- 체스판에서 나이트가 목표 위치까지 도달하는 최소 이동 횟수
- 단어 변환 문제: 한 번에 한 글자씩만 바꿔 시작 단어를 목표 단어로 변환하는 최소 단계
- 격자(Grid) 기반 탐색
- 섬의 개수 세기: 연결된 땅을 하나의 섬으로 카운트
- 감염 확산: 바이러스가 상하좌우로 퍼져나가는 시간 계산
- 불이나 물이 퍼지는 시뮬레이션
- 레벨별 처리가 필요한 문제
- 트리의 레벨 순회
- 특정 거리의 도시 찾기: 출발 도시로부터 정확히 K 거리에 있는 모든 도시 찾기
- 특정 거리 내의 모든 노드 찾기
DFS로 해결하기 좋은 코딩 테스트 문제
- 완전 탐색 및 백트래킹
- 순열과 조합 생성
- N-Queen 문제
- 스도쿠 풀이
- 부분 집합의 합(Subset Sum) 문제
- 그래프 관련 문제
- 사이클 감지
- 위상 정렬: 선수과목을 고려한 수업 순서 결정
- 이분 그래프 판별
- 연결 요소의 개수 찾기
- 깊이가 중요한 탐색
- 경로 존재 여부 확인
- 모든 가능한 경로 찾기
- 미로 생성 알고리즘
BFS와 DFS는 코딩 테스트의 단골 주제로, 이 두 알고리즘을 제대로 이해하고 활용할 수 있다면 많은 알고리즘 문제를 효과적으로 해결할 수 있습니다. 문제의 요구사항을 정확히 분석하여 적절한 알고리즘을 선택하는 능력을 키우는 것이 중요합니다. 지속적인 문제 풀이 연습을 통해 그래프 탐색 알고리즘의 활용 능력을 향상해 보시기 바랍니다.