[SW 정글 20일차] 위상 정렬 (Topological Sort)

오늘은 위상 정렬에 대해 정리해보려고 한다.

처음 듣는 알고리즘이여서 오늘 이렇게 공부를 하고 다시 복습을 하며 내 것으로 만들어야겠다.

 

 

 

1. 위상 정렬 (Topological Sort)

위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

순서가 정해져있는 작업에서 각 작업들은 직전 작업에 의존하게 된다.

예를 들어 C라는 작업을 끝내기 위해서는 A작업과 B작업이 끝나야지만 가능하다고 해보자.

C는 A와 B가 끝날때까지 일을 실행하지 못하므로 A와 B에게 의존하고 있다고 볼 수 있다.

 

여기서 위상 정렬이 순서를 결정해준다고 했지만 그 순서가 딱 하나만 존재하는 것은 아니다.

위에서 든 예시만 봐도 A -> B -> C가 될 수 있고 B-> A -> C가 될 수 있기 때문이다.

 

위상정렬은 깊이 우선 탐색(DFS)로 풀 수 있는 대표적인 정렬 방법으로 정렬하고자 하는 그래프는 의존성 그래프(Dependency Graph)여야한다.

출처: https://reakwon.tistory.com/140

의존성 그래프는 각 정점의 의존 관계를 간선으로 나타낸 방향 그래프이다.

만약 작업 v는 u가 끝나야만 수행할 수 있다면 그래프는 u->v로 향하는 간선을 포함하게 된다.

이러한 의존성 그래프에서 위상 정렬을 하기 위해서는 사이클이 존재하지 않아야한다.

(즉, DAG(Direted Acyclic Graph)에만 위상 정렬이 적용가능하다는 것이다.)

 

위에서 본 그래프는 사이클이 존재하지 않아 위상 정렬이 가능하지만 아래의 그림과 같이 사이클이 존재하면 어떻게 될까?

위상 정렬을 하기 위해서는 시작점이 존재해야 하는데 그래프에 사이클이 존재하면 시작점부터 찾을 수가 없게 된다.

이러한 위상 정렬의 시간복잡도는 O(V + E)이다.

(V: 정점의 개수, E: 간선의 개수)

 

 

위상 정렬을 수행하는 알고리즘은 스택 자료구조를 이용하는 방식과 큐 자료구조를 이용하는 방식이 있다.

먼저, 큐 자료구조를 이용하는 방식이다.

① 위상 정렬을 시작하기 전에 각 정점과 진입차수 정보를 저장한다.

(진입 차수: 한 정점으로 들어오는 간선의 개수)

② 진입차수가 0인 정점을 큐에 삽입한다.

③ 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.

④ 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다.

⑤ 큐가 빌 때까지 3 ~ 4번 과정을 반복한다. 만약에 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과가 된다.

 

※ 큐를 이용하여 위상 정렬을 하는 그림은 아래의 블로그에서 볼 수 있다.

https://m.blog.naver.com/ndb796/221236874984

 

그러면 큐를 이용한 위상 정렬을 코드로 구현해보자.

def topological_sort_queue(adj_list):
    import queue

    myQue = queue.Queue()
    in_degree = [0] * len(adj_list)
    answer = []

    for i in range(len(adj_list)):
        for j in range(len(adj_list)):
            temp = adj_list[j]
            for k in range(len(temp)):
                if temp[k] == i:
                    in_degree[i] += 1
    print("in_degree 배열: ", in_degree)

    for i in range(len(in_degree)):
        if in_degree[i] == 0:
            myQue.put(i)

    print("초기 스택: ", myQue)
    while not myQue.empty():
        node = myQue.get()
        answer.append(node)
        print("pop 된 노드: ", node)

        for i in range(len(adj_list[node])):
            idx = adj_list[node][i]
            in_degree[idx] -= 1
            if in_degree[idx] == 0:
                myQue.put(idx)

    print("answer: ", answer)


print(topological_sort_queue(adj_list))

 

 

다음으로 스택 자료구조를 이용하는 방식이다.

① 위상 정렬을 시작하기 전에 각 정점과 진입차수 정보를 저장한다.

② 진입차수가 0인 정점을 스택에 삽입한다.

③ 스택에 들어 있는 것을 pop해서 꺼낸 노드에서 갈 수 있는 노드의 진입 차수를 1 감소시키고 진입 차수가 0이 되면 해당 노드를 스택에 넣는다.

⑤ 스택이 빌 때까지 3번 과정을 반복한다. 만약에 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고 모든 원소를 방문했다면 스택에서 꺼낸 순서가 위상 정렬의 결과가 된다.

 

스택을 이용하여 위상 정렬을 하는 그림은 아래의 블로그에서 볼 수 있다.

https://sexy-developer.tistory.com/56

 

그러면 스택을 이용한 위상 정렬을 코드로 구현해보자.

def topological_sort_stack(adj_list):
    stack = []
    in_degree = [0] * len(adj_list)
    answer = []

    for i in range(len(adj_list)):
        for j in range(len(adj_list)):
            temp = adj_list[j]
            for k in range(len(temp)):
                if temp[k] == i:
                    in_degree[i] += 1

    print("in_degree 배열: ", in_degree)

    for i in range(len(in_degree)):
        if in_degree[i] == 0:
            stack.append(i)

    print("초기 스택: ", stack)
    while stack:
        node = stack.pop()
        answer.append(node)
        print("pop 된 노드: ", node)

        for i in range(len(adj_list[node])):
            idx = adj_list[node][i]
            in_degree[idx] -= 1
            if in_degree[idx] == 0:
                stack.append(idx)

    print("answer: ", answer)


print(topological_sort_stack(adj_list))

---

[오늘의 나는 어땠을까?]

오늘도 어김없이 DFS, BFS 알고리즘 문제 풀이를 했다.

오늘 푼 문제는 총 3문제인데 오늘 강의실에 온 시간은 아침 8시이고 이 글을 쓰기 시작한 것은 12시 30분이다.

그러면 밥먹는 시간 2시간을 제외하고 휴식시간 1~2시간 제외하면 10시간 정도 컴퓨터 앞에 앉아서 알고리즘 문제 풀이에 시간을 투자한 것이다.

10시간이면 꽤 많은 시간이지만 정량적인 양으로 봤을 때 푼 문제가 3문제라는 것이 조금 기분이 묘했다.

물론, 한 문제를 풀기 위해 오랫동안 고민해보는 것은 좋지만 뭔가 그냥 그랬다.

문제를 해결하기 위해 내가 고민하는 시간을 줄여보고 접근 방식을 배우는 식으로 해야겠다는 생각이 들었다.

 

그리고 오늘은 SW 정글 1기 수료생에게 간단한 질문을 이메일로 보내 답장을 받았다.

너무 장황한 질문들이였지만 정말 친절하게 공감을 해주면서 답변을 주셨고 조금이나마 위로가 되었고 의지가 더 오를 수 있었다.

1기 수료생들이 됐으니까 나도 되겠지라는 생각을 가진 것이 아니라 나도 충분히 최선을 다하고 열심히 해보면 단기적인 목표를 이룰 수 있다는 생각이 들었다.

 

알고리즘 주차가 끝나고 다시 팀 프로젝트로 B트리, 말록랩, PintOS 구현에 들어가기 전에 시간관리를 잘해서 나의 성장에 포커스를 두어야겠다.

 

---

<참고 자료>

https://sexy-developer.tistory.com/56

https://reakwon.tistory.com/140

https://jason9319.tistory.com/93

https://m.blog.naver.com/ndb796/221236874984