C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

A,B,C,D,E 작업들은 선행작업에 대한 의존성을 가지고 있으므로, 방향그래프로 표현될 수 있다. 즉, C->A, D->C, D->E 등과 같이 표현될 수 있다. 먼저 그래프 g 객체를 생성하고, 데이타와 방향을 나타내는 Edge를 아래와 같이 표현할 수 있다. 여기서는 그래프를 Adjacency list로 표현하고 있다.

static void RunTest()
{
    Graph g = new Graph();

    GraphNode A = new GraphNode("A");
    GraphNode B = new GraphNode("B");
    GraphNode C = new GraphNode("C");
    GraphNode D = new GraphNode("D");
    GraphNode E = new GraphNode("E");

    g.GraphNodes.AddRange(new[] { A, B, C, D, E });

    D.AddEdge(C);
    E.AddEdge(C);
    D.AddEdge(E);
    C.AddEdge(A);
    C.AddEdge(B);

    var result = g.TopologicalSort();

    foreach (var n in result)
    {
        Console.WriteLine(n.Data);
    }
} 

위와 같이 그래프로 표현되었으면, 이제 어떤 작업이 먼저 실행되어야 하는지를 나타내기 위해 의존 관계에 따른 정렬을 하게 되는데, 이를 Topological Sorting 혹은 Topological Ordering이라 부른다. 이 알고리즘의 한 방법으로 아래는 DFS (Depth First Search)를 사용하는 예를 보여준다.

TopologicalSort() 메서드에서 보이듯이, 우선 모든 노드를 차례로 방문하는데 이미 방문된 노드들을 건너뛴다. 방문하는 각 노드들 하나씩에 대해 DFS를 실행하게 된다. DFS를 구현한 Visit() 메서드에서는 각 이웃노드들에 대해 다시 Visit() 메서드를 재귀호출하고 있다. 여기서 중요한 점은 결과를 스택에 추가하는 문장이 재귀호출(Recurisve) 이후에 있다는 점이다. 이것은 그래프 노드 방향을 따라가며 가장 마지막에 있는 노드를 먼저 결과리스트에 추가하는 역할을 한다. 결과는 스택에 저장되므로 소트결과가 실제 출력될 때는 역순으로 출력되어 원하는 결과를 출력하게 된다.

class Graph
{
    private List<GraphNode> _nodes = new List<GraphNode>();
    private Stack<GraphNode> _sortResult;

    public List<GraphNode> GraphNodes
    {
        get { return this._nodes; }
    }

    public IEnumerable<GraphNode> TopologicalSort()
    {
        this._sortResult = new Stack<GraphNode>();

        // clear visited
        foreach (var gnode in this.GraphNodes)
        {
            gnode.Visited = false;
        }

        // Visit
        foreach (var v in this.GraphNodes)
        {
            if (!v.Visited) Visit(v);
        }

        return _sortResult;
    }

    void Visit(GraphNode n)
    {
        n.Visited = true;

        foreach (var v in n.Neightbors)
        {
            if (!v.Visited) Visit(v);
        }
            
        this._sortResult.Push(n); // Add to result    
    }
}

class GraphNode
{
    public GraphNode(object data)
    {
        this.Data = data;
    }

    public object Data { get; set; }

    public bool Visited { get; set; }

    public List<GraphNode> Neightbors
    {
        get { return this.neightbors; }
    }

    public void AddEdge(GraphNode to)
    {
        this.Neightbors.Add(to);
    }

    private List<GraphNode> neightbors = new List<GraphNode>();
}