정의

그래프 탐색(DFS, BFS)은 그래프에서 특정 노드를 방문하고 탐색하는 방법을 의미한다. DFS(깊이 우선 탐색)는 한 노드를 시작으로 최대한 깊이 들어간 후 다시 돌아오는 방식이며, BFS(너비 우선 탐색)는 시작 노드에서 가까운 노드부터 탐색하는 방식

특성

• DFS (Depth-First Search)
• 스택 또는 재귀 함수 사용
• 깊은 경로를 먼저 탐색
• 백트래킹 활용 가능

알고리즘 순서

1. 시작 노드를 방문하고 스택(또는 재귀 호출)으로 저장
2. 현재 노드에서 방문하지 않은 인접 노드 탐색
3. 방문하지 않은 노드가 있다면 해당 노드로 이동
4. 방문할 노드가 없으면 되돌아감 (백트래킹)
5. 모든 노드를 방문할 때까지 반복

활용 예시

• 미로 그래프
• 그래프 연결 요소 찾기
• 백트래킹 기반 문제 해결

문제 (백준)

4963 (섬의 개수)

10026 (적록색약)