숏컷 코드
csharp
void Dfs(int current)
{
visited[current] = true;
foreach (int next in graph[current])
{
if (visited[next]) continue;
Dfs(next);
}
}구조
DFS는 가능한 한 깊이 내려간 뒤, 더 갈 곳이 없으면 이전 상태로 돌아옵니다. 그래프 연결 요소, 트리 순회, 사이클 탐지, 백트래킹의 기본 흐름으로 자주 쓰입니다.
text
현재 정점 방문
갈 수 있는 다음 정점 선택
끝까지 내려감
돌아와서 다른 후보 탐색재귀 구현은 간단하지만, 입력이 깊으면 콜 스택을 넘길 수 있습니다. 이때는 Stack<T>로 직접 구현합니다.
csharp
var stack = new Stack<int>();
stack.Push(start);
while (stack.Count > 0)
{
int current = stack.Pop();
if (visited[current]) continue;
visited[current] = true;
foreach (int next in graph[current])
{
if (!visited[next]) stack.Push(next);
}
}BFS와 비교
| 기준 | DFS | BFS |
|---|---|---|
| 처리 순서 | 깊게 먼저 | 가까운 거리 먼저 |
| 자료구조 | 재귀 또는 스택 | 큐 |
| 최단 거리 | 일반적으로 보장 안 함 | 무가중 그래프에서 보장 |
| 대표 용도 | 연결 요소, 순회, 백트래킹 | 최단 이동, 단계별 확산 |
DFS는 답을 찾으면 바로 깊게 들어갈 수 있지만, 최단 거리를 요구하는 문제에서는 틀릴 수 있습니다. “모든 경우를 탐색”, “연결되어 있는지 확인”, “가능한 조합 생성” 같은 문제에 더 잘 맞습니다.
주의할 점
무방향 그래프에서 사이클을 검사할 때 단순히 방문한 정점을 다시 만났다고 모두 사이클은 아닙니다. 바로 직전 부모 정점으로 돌아가는 간선은 제외해야 합니다.
또 C# 코테 환경에서 재귀 깊이가 매우 깊으면 스택 오버플로가 날 수 있습니다. 정점 수가 크고 경로처럼 긴 그래프라면 반복 DFS를 우선 검토하세요.
참고 링크
1 sources