DFS 기반 사이클 검출 (Recursion Stack 방식)

1. 개념 정리

1.1 문제 정의

유향 그래프에서 “사이클이 존재하는가(즉, 순환참조가 있는가)?”를 묻는 문제입니다. 만약 사이클이 없다면 그 그래프는 DAG이고, 순환 참조 문제(예: A → B → C → A)로부터 자유롭습니다. (GeeksforGeeks)
예컨대, 의존성 그래프(모듈간, 이벤트간, 반응형 흐름간)에서 순환 참조가 생기면 무한 루프나 예측불가능한 상태를 만들 수 있기 때문에, 게임 개발 등 반응형 프로그래밍 환경에서도 이 검사가 중요합니다.

1.2 왜 DFS + 재귀 스택 방식인가?

• DFS 진행 중에 **현재 탐색 경로상에 있는 노드(recursion stack)**에 다시 도달하면, 그 경로상에서 부모 → … → 자식 → 다시 부모(혹은 조상)로 이어지는 간선(back edge)이 있다는 뜻이며, 이는 사이클이 있다는 증거입니다. (GeeksforGeeks)
• 단순히 “이미 방문(visited)”만 체크하면, 다른 경로에서 이미 탐색된 노드도 방문 처리돼있을 수 있고, 그것이 반드시 같은 탐색 경로상에서의 조상 노드라는 뜻이 아닙니다. 따라서 별도로 “현재 호출 스택상에 있는 노드(recursion stack)” 정보를 유지해야 합니다. (w3schools.com)
• 시간복잡도는 모든 정점(V)과 간선(E)에 대해 탐색하므로 **O(V + E)**입니다. (GeeksforGeeks)
• 공간복잡도도 방문 배열 + 재귀 스택 정보 + 재귀 호출 오버헤드로 O(V) 수준입니다. (Medium)

1.3 알고리즘 흐름

아래는 유향 그래프에서 DFS+재귀스택 방식으로 사이클을 검출하는 일반적인 흐름입니다:

1. 그래프를 인접리스트 형태로 표현한다. (예: 각 노드 → 자식노드 리스트)
2. visited[] 배열을 생성하고, 모든 노드는 아직 방문되지 않은 상태로 초기화.
3. recStack[] (혹은 Boolean 배열)도 생성하여, 현재 DFS 호출 중인 경로에 있는 노드를 표시한다.
4. 모든 노드 u에 대해 (만약 visited[u] == false이면) 다음을 실행:
   • DFSUtil(u) 호출
5. DFSUtil(u) 함수 내부:
   • visited[u] = true, recStack[u] = true
   • 자식 노드들 v 각각에 대해:
     • 만약 visited[v] == false, 재귀 호출 DFSUtil(v). 만약 이 호출에서 사이클이 발견됐다면 true를 리턴 → propagate
     • 그렇지 않은데 recStack[v] == true라면 → v가 현재 호출 경로상에 있으므로 사이클 발견 → return true
   • 자식 탐색이 끝나면: recStack[u] = false (현재 경로에서 u를 제거)
   • return false (u에서 시작해 사이클을 발견하지 못한 경우)
6. 만약 어느 노드에서라도 true가 리턴되면 “사이클 존재”이고, 전체 탐색이 끝나고도 발견되지 않으면 “사이클 없음 → DAG”입니다.

이를 더 요약하면 “DFS 중 리턴 경로상에 있는 노드를 다시 방문하면(back edge) 사이클”이라는 개념입니다. (GeeksforGeeks)

1.4 왜 DAG 검증에 적합한가?

• DAG란 순환이 없는 유향 그래프이므로, “사이클 있는가?”가 바로 “DAG인가?” 판별의 핵심입니다.
• 의존성 그래프, 반응형 흐름 그래프 등에서 순환참조가 있으면 유지보수·디버깅이 어렵기 때문에, 이런 검사를 런타임 혹은 빌드타임에 둘 수 있습니다.
• DFS+재귀스택 방식은 구현이 비교적 간단하고, O(V+E)로 효율적이기 때문에 규모가 어느 정도 있는 그래프에서도 충분히 사용 가능합니다.

---

2. 구현 팁 및 유의사항

아래는 게임 개발 · 특히 Unity + C# 환경에서 이 알고리즘을 적용할 때 유의할 점과 팁입니다.

2.1 그래프 구성

• 당신이 반응형 프로그래밍 환경에서 만든 “노드” 혹은 “컴포넌트” 간의 의존성(예: 이벤트 흐름, 옵저버 패턴) 관계를 유향 그래프로 모델링해야 합니다.
• 노드 식별자(예: 컴포넌트 인스턴스 ID 또는 타입명 등)를 인덱스/키로 사용해서, Dictionary<Node, List<Node>> adjList 같이 인접리스트를 구성할 수 있습니다.
• 노드가 동적으로 추가/삭제되는 환경이라면, 그래프를 구성할 때 최신 상태 반영이 중요합니다.

2.2 C# 구현 기본 구조

C#에서 위 흐름을 구현하면 다음과 같은 형태가 될 수 있습니다:

public class Graph<T>
{
    private Dictionary<T, List<T>> _adjacency = new Dictionary<T, List<T>>();

    // 노드 추가 혹은 엣지 추가 메서드
    public void AddEdge(T from, T to)
    {
        if (!_adjacency.ContainsKey(from))
            _adjacency[from] = new List<T>();
        _adjacency[from].Add(to);

        // 필요하다면 to 노드도 키로 존재하게 초기화
        if (!_adjacency.ContainsKey(to))
            _adjacency[to] = new List<T>();
    }

    public bool HasCycle()
    {
        var visited = new Dictionary<T, bool>();
        var recStack = new Dictionary<T, bool>();

        // 초기화
        foreach (var node in _adjacency.Keys)
        {
            visited[node] = false;
            recStack[node] = false;
        }

        foreach (var node in _adjacency.Keys)
        {
            if (!visited[node])
            {
                if (HasCycleUtil(node, visited, recStack))
                    return true;
            }
        }
        return false;
    }

    private bool HasCycleUtil(T node, Dictionary<T, bool> visited, Dictionary<T, bool> recStack)
    {
        visited[node] = true;
        recStack[node] = true;

        foreach (var neighbor in _adjacency[node])
        {
            if (!visited[neighbor] && HasCycleUtil(neighbor, visited, recStack))
            {
                return true;
            }
            else if (recStack[neighbor])
            {
                // 현재 경로 상에 있는 노드에 다시 왔으면 사이클
                return true;
            }
        }

        recStack[node] = false;
        return false;
    }
}

위 코드는 제네릭 타입 T를 받아서 노드 타입을 자유롭게 쓸 수 있게 했고, 기본적인 visited + recursion-stack 구조를 갖추고 있습니다. (참고: C# 예제가 참고된 글이 있습니다) (C# Corner)

2.3 Unity 환경 특별히 고려할 점

• Unity에서는 노드나 컴포넌트가 MonoBehaviour이거나 ScriptableObject일 가능성이 높습니다. 이런 객체들은 Equals/GetHashCode나 참조 형태를 고려해야 하므로, 위 제네릭 T가 적절히 식별 가능해야 합니다 (예: 문자열 키, 혹은 고유 ID).
• 반응형 프로그래밍(flow)에서는 의존관계가 런타임에 동적으로 바뀔 수 있으므로, 그래프 검증 시점(예: 초기화 시, 빌드 시, 변경 직후 등)을 명확히 해야 합니다.
• ノ드 수가 많거나 엣지가 자주 바뀐다면, 재검증 비용이 있으므로 최신 변경만 검토하는 증분 검증 방식도 고려할 수 있습니다. (이건 고급사항)
• Unity의 메인 스레드/비동기 흐름을 고려할 때, DFS 재귀가 깊어질 수 있으므로 스택 오버플로우 위험을 염두에 두고, 노드 수가 크면 반복(스택) 방식이나 색상 방식(white/gray/black) 구현도 고려해볼 수 있습니다. (GeeksforGeeks)

2.4 추가 - 색상 방식(Coloring)

방식 하나로는 ‘재귀 스택’ 대신 노드에 상태(white: 미방문, gray: 현재 경로, black: 완전탐색 완료)를 부여하는 색상 알고리즘이 있습니다.

• 노드를 방문할 때 → gray로 변경
• 탐색 자식 중에 gray 상태인 노드가 있다면 사이클 존재
• 자식 탐색 완료되면 → black로 변경
  이 방식도 본질적으로 동일하며, 구현에 따라 더 명시적이거나 오류가 적은 경우가 많습니다. (GeeksforGeeks)

2.5 유의사항 및 예외

• 자기자신으로 향하는 간선(self-loop)은 즉시 사이클입니다. (tutorialspoint.com)
• 그래프가 비연결된(disconnected) 경우에도 각 컴포넌트마다 DFS를 실행해야 합니다. (GeeksforGeeks)
• 단순히 visited만 체크하고 recStack 체크 안하면 **오탐(false positive)**이 생길 수 있습니다. (이미 다른 경로에서 방문된 노드를 현재 경로조상이라 오인) (w3schools.com)
• 재귀 깊이가 노드 수만큼 될 수 있으므로 깊은 그래프에서는 스택 깊이나 성능에 유의해야 합니다.

---

3. Unity/C# 환경에서 적용 방향

마지막으로, “반응형 프로그래밍 환경에서 순환참조 문제”를 검증하기 위해 이 알고리즘을 실제로 Unity + C# 프로젝트에 적용하는 방향성을 몇 가지 제안드립니다.

3.1 그래프 모델링

• 각 반응형 노드(예: 옵저버, 이벤트 발신자·수신자, 바인딩 대상)를 그래프의 노드로 본다.
• 노드 A가 노드 B에 의존하거나 메시지를 보내면 A → B 형태로 유향 간선을 만든다.
• 전체 관계가 집합으로 모이면 이 그래프에서 사이클이 있는지 검사하면 순환참조 여부를 확인할 수 있다.

3.2 검증 타이밍

• 초기화 시: 게임 시작 전에 모든 노드의 의존관계를 구성하고, 한 번 순환체크를 실행하면 런타임 오류 가능성 줄일 수 있습니다.
• 런타임 변경 시: 만약 노드/관계가 동적으로 추가된다면, 변경 후 즉시 해당 부분만(혹은 전체) 순환체크를 실행하는 것이 좋습니다.
• 에디터 타임(빌드 전): 가능하다면 에디터 스크립트로 검사해서 순환참조를 사전에 방지하는 것도 좋은 방법입니다.

3.3 성능 최적화

• 노드 수가 많거나 관계가 복잡하면 전체 DFS가 부담이 될 수 있습니다. 이럴 땐 변경된 노드 주변만 탐색하거나 증분 알고리즘(새로운 엣지가 추가됐을 때만 검사)도 고려할 수 있습니다.
• 재귀 깊이가 너무 크면 Unity 환경에서 스택 오버플로우 가능성이 있으므로, 필요에 따라 비재귀 버전 또는 색상 기반 알고리즘으로 대체할 수 있습니다.

3.4 에러 처리 및 디버깅

• 사이클을 발견했을 때 어떤 노드들이 루프에 관여했는지 로그로 남기면 디버깅에 매우 도움이 됩니다.
• 예컨대, 재귀 호출 스택에 있는 노드를 추적해서 “A → B → C → A” 형태로 출력해주면 어떤 참조가 잘못됐는지 직관적으로 파악할 수 있습니다.
• Unity 에디터 내부에서 그래프 시각화 도구를 만들어서, 순환참조가 있는 노드를 하이라이트하거나 링크 그래프를 보여주는 것도 장기적으로 유리합니다.