Quick Flow
한 경로를 끝까지 따라가며 연결 여부, 구성 요소, 가능한 상태를 찾을 때 DFS를 씁니다. 무가중 최단 거리는 DFS가 아니라 BFS의 역할입니다. 그래프가 끊어져 있을 수 있으면 시작점 하나가 아니라 모든 정점에서 DFS를 시작해야 합니다.
static void VisitAll(IReadOnlyList<int>[] graph)
{
var visited = new bool[graph.Length];
for (int start = 0; start < graph.Length; start++)
{
if (!visited[start]) Visit(start, graph, visited);
}
}
static void Visit(int current, IReadOnlyList<int>[] graph, bool[] visited)
{
visited[current] = true;
foreach (int next in graph[current])
{
if (visited[next]) continue;
Visit(next, graph, visited);
}
}- 연결 요소·순회·백트래킹: DFS
- 최소 간선 수·단계별 확산: BFS
- 재귀 깊이가 정점 수까지 커질 수 있음:
Stack<T>반복 구현 검토
구조
DFS는 가능한 한 깊이 내려간 뒤, 더 갈 곳이 없으면 이전 상태로 돌아옵니다. 그래프 연결 요소, 트리 순회, 사이클 탐지, 백트래킹의 기본 흐름으로 자주 쓰입니다.
현재 정점 방문
갈 수 있는 다음 정점 선택
끝까지 내려감
돌아와서 다른 후보 탐색재귀 구현은 간단하지만, 입력이 깊으면 콜 스택을 넘길 수 있습니다. 이때는 Stack<T>로 직접 구현합니다. 두 구현의 방문 순서는 인접 정점 순서와 push 순서에 따라 달라질 수 있지만, 각 정점과 간선을 한 번씩 확인하므로 시간은 O(V + E)입니다.
static void VisitIteratively(IReadOnlyList<int>[] graph, int start, bool[] visited)
{
var stack = new Stack<int>();
stack.Push(start);
while (stack.TryPop(out int current))
{
if (visited[current]) continue;
visited[current] = true;
foreach (int next in graph[current])
{
if (!visited[next]) stack.Push(next);
}
}
}BFS와 비교
| 기준 | DFS | BFS |
|---|---|---|
| 처리 순서 | 깊게 먼저 | 가까운 거리 먼저 |
| 자료구조 | 재귀 또는 스택 | 큐 |
| 최단 거리 | 일반적으로 보장 안 함 | 무가중 그래프에서 보장 |
| 대표 용도 | 연결 요소, 순회, 백트래킹 | 최단 이동, 단계별 확산 |
DFS는 답을 찾으면 바로 깊게 들어갈 수 있지만, 최단 거리를 요구하는 문제에서는 틀릴 수 있습니다. “모든 경우를 탐색”, “연결되어 있는지 확인”, “가능한 조합 생성” 같은 문제에 더 잘 맞습니다.
사이클 조건
무방향 그래프는 방금 온 부모 정점으로 되돌아가는 간선을 제외하고 방문한 정점을 다시 만나면 사이클입니다. 방향 그래프는 방문 완료 정점과 현재 재귀 경로의 정점을 구별해야 합니다. 회색(방문 중) 정점으로 가는 간선만 방향 사이클을 뜻합니다.
static bool HasDirectedCycle(IReadOnlyList<int>[] graph)
{
var state = new int[graph.Length]; // 0: 미방문, 1: 방문 중, 2: 완료
bool Search(int current)
{
state[current] = 1;
foreach (int next in graph[current])
{
if (state[next] == 1) return true;
if (state[next] == 0 && Search(next)) return true;
}
state[current] = 2;
return false;
}
for (int start = 0; start < graph.Length; start++)
{
if (state[start] == 0 && Search(start)) return true;
}
return false;
}주의할 점
무방향 그래프에서 사이클을 검사할 때 단순히 방문한 정점을 다시 만났다고 모두 사이클은 아닙니다. 바로 직전 부모 정점으로 돌아가는 간선은 제외해야 합니다. 반대로 방향 그래프에 이 규칙을 가져오면 순환 간선을 놓치므로 3색 상태나 재귀 경로 집합을 사용합니다.
또 C# 코테 환경에서 재귀 깊이가 매우 깊으면 스택 오버플로가 날 수 있습니다. 정점 수가 크고 경로처럼 긴 그래프라면 반복 DFS를 우선 검토하세요.
참고 링크
1 sources