[알고리즘 자습]그래프(Graph) - 3. 위상 정렬, 파이썬(Python3)

앞선 게시물들에서, 

• 0. 그래프 자료구조
• 1. BFS, 너비우선 탐색
• 2. DFS, 깊이우선 탐색

이 3가지에 대한 정의와 활용을 예제를 통해 알아보면서 정리했다. 이 정도 수준의 알고리즘을 알았다면, 우리는 그래프에 관해서는 어느정도 잘 이해하고 있다고 봐도 좋다. 그렇기 때문에, 그래프 알고리즘 중 하나인 위상 정렬에 대해 아주 쉽게 알아볼 수 있다. 알아서 나쁠거 하나도 없고, 위상 정렬을 이용해 문제를 풀면 BFS, DFS보다 쉽게 풀리는 문제도 있다. 따라서, 우리는 충분히 위상 정렬에 대해 알아볼 필요가 있다. 

 

위상 정렬

위상 정렬에 대해 설명하기 전에, 단어를 먼저 이해하고 시작하는 것이 좋을 것 같다. 

 

우리는 살면서 알게 모르게 위상이라는 단어를 많이 써왔다. 누구누구의 사회적 위상이 어떻다 라든가, 불교의 종교적 위상이 높아졌다 이런 식으로 말이다. 그런데 이러한 단어가 컴퓨터 공학의 알고리즘 분야에서 나오는 것이 살짝 이상하다. 그래서 위상이라는 단어 뜻을 어학 사전에 쳐본 결과가 아래의 캡처이다. 

출처: 네이버 어학사전

위상이라 함은, '어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태'를 말한다. 여기서, 우리가 그 전까지 알아봤던 그래프 자려구조와의 접점이 나타난다. 사물이라는 말을 정점으로 바꾸면, '어떤 정점이 다른 정점과의 관계속에서 가지는 위치나 상태'가 된다. 뭔가 감이 올것만 같다. 

위상 정렬을 이용해 문제를 해결하는 알고리즘을 만들고 싶은 우리에게 맞게 설명하자면, 위상 정렬이란 각 정점들이 가지는 위상(다른 정점과의 관계, 즉 간선)에 따라서, 그래프를 구성하는 정점들을 순서대로 정렬해서 결과값으로 출력하는 것이다. 

사실 이렇게 위상 정렬이라는 단어를 최대한 쉽게 풀어서 이야기하려는 이유는, 위키에 나와있는 설명이 너무 와닿지 않아서이다. 위키에서는 '유향 그래프의  꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.' 라고 하는데, 이게 맞는 말이긴 한데 위상 정렬에 대해 처음 들어보는 사람들은 이해하기가 힘들 것 같아서, 내가 쉽게 이해하기 위해서 좀 쉽게 풀어서 써봤다. 잘 이해가 안된다면, 그냥 아래 링크로 가서 읽어보기 바란다https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬 - 위키백과, 우리 모두의 백과사전

위상 정렬의 사용 예로 무조건 나오는 것이 대학교의 선수과목 구조이다. 컴퓨터란 무엇인가, 네트워크, 이산수학, C언어, 자료구조, 알고리즘, 컴파일러, 자바, 도메인 분석및 설계 등 여러 과목이 있는데, 우리는 'C언어도 안듣고 알고리즘 수업을 들을 수 없다', '컴퓨터란 무엇인가 과목을 수강하지 않고는 C언어를 수강할 수 없다' 이런 규칙들을 잘 지켜서 수강 신청을 해야 한다. 이러한 관계를 '위상'이라 하고, 이 위상에 따라서 과목들을 쭉 정렬하게 되면, '컴퓨터란 무엇인가, 이산수학, C언어, 자료구조, 알고리즘 .... 도메인 분석 및 설계' 이런 순서로 정렬된 배열이 결과로 나온다. 

즉, 어떤 그래프를 위상 정렬하게 되면, 그 결과로 정점들을 위상적 순서대로 정렬한 배열이 나오게 된다. 근데 아마 이렇게 얘기를 해도 이해가 잘 되지 않을 것이다. 왜냐면 나도 이 글만 보고는 무슨 소린지 모르겠으니까. 그러니까 이정도로 보고, 코드를 짜서 알아보도록 하자. 

 

위상 정렬의 조건

주어진 그래프에서 위상 정렬을 하려면, 아래와 같은 조건을 만족하는 그래프여야 한다. 

1. 위상 정렬을 할 그래프는 간선이 방향성을 가지는(유향) 그래프여야 한다.
2. 그래프 내부에 순환(cycle)이 있으면 안된다. 

 

알고리즘

위상 정렬의 기본 아이디어는 다음과 같다.

• 각 정점들의 진입차수(In-degree)를 이용한다. 진입 차수란, 한 정점으로 들어오는 간선의 갯수를 말한다. 진출 차수와 반대되는 단어이다.
• 각 정점들의 진입 차수를 한 배열에 저장해놓는다. 

말로 간단하게 이야기 해보면 이렇다. 초기 스택에 진입 차수가 0인 노드를 집어넣고, 하나씩 꺼내보면서, 꺼낸 노드에서 갈 수 있는 노드의 진입 차수를 1 감소시키고, 진입 차수가 0이 되면 그 노드를 스택에 집어넣는 것이다.

그림으로 나타내면 아래와 같다. 

위 그래프를 위상 정렬할 것이다. 말했듯이, 진입 차수가 0인 노드 0, 1을 스택에 넣는다. 

 

stack에서 하나의 정점을 pop한다. 그럼 1이 나오게 되는데, 그 1과 인접한 정점의 진입차수를 1씩 감소시킨다. 그리고 진입 차수가 0이 된 정점을 스택에 집어넣는다. 그럼 아래와 같은 결과가 나온다. 

 

 

그리고 다음엔 4가 pop되고, 4와 인접한 노드의 진입 차수를 1 감소시킨다. 

 

 

그리고, stack에 있는 0에 pop 되고, 0에서 갈 수 있는 2, 3번 정점의 진입 차수를 1 감소시킨다. 그럼 2번 정점의 진입 차수가 0이 되어 스택에 들어간다. 

 

 

2를 pop하고, 연결된 노드의 진입 차수를 1씩 감소시킨다. 그럼 3이 진입 차수가 0이 되어 스택에 들어간다. 

 

3를 pop하고, 연결된 노드의 진입 차수를 1씩 감소시킨다. 그럼 5가 진입 차수가 0이 되어 스택에 들어간다. 

 

 

5가 스택에 들어갔다가 pop되고, 연결된 노드가 없어서 더이상 스택에 원소를 집어넣지 못하므로 반복이 종료된다. 이때 pop된 노드들을 순서대로 answer 배열에 담아놓으면 정답이 나온다. 

 

 

 

이를 의사 코드로 나타내면 아래와 같다. 

1. in_degrees 배열에 각 정점의 진입 차수를 저장한다.
2. 진입 차수가 0인 정점을 stack(또는 queue)에 저장한다.   
   -> 스택을 쓸지 큐를 쓸지에 따라 결과가 다르게 나타난다. 이는 아래에서 확인할 것이고, 일단은 스택을 사용한다고 가정하자. 
3. in_degrees 배열을 돌면서, 진입 차수가 0인 정점을 stack에 push한다.
4. stack에 원소가 있을 동안, 아래 과정을 반복한다.
   1. stack에서 pop한 정점을 node에 저장한다. 
   2. node에서 갈 수 있는 정점을 i라 할 때, 가능한 모든 i에 대한 in_degrees[i]의 값을 1 감소시킨다. 즉, i 정점의 진입 차수를 1 감소시킨다. 
   3. i의 진입 차수가 0이 되었다면, i를 stack에 넣는다. 

 

알고리즘

총 4개의 코드가 나온다. 

• 답안1: 인접 행렬 형태의 인풋 그래프를 위상 정렬하는 코드(스택 사용)
• 답안2: 인접 리스트 형태의 인풋 그래프를 위상 정렬하는 코드(스택 사용)
• 답안3: 인접 리스트 형태의 인풋 그래프를 위상 정렬하는 코드(큐 사용)
• 응용1: 큐를 통해 동일한 위상 지니는 노드는 하나의 배열로 묶어서 출력하는 코드

 

답안 1: 인접 행렬 형태의 그래프를 위상 정렬(스택 사용)

"""
주어진 그래프의 인접행렬을 바탕으로, 위상 정렬을 한다
입력: 그래프의 인접행렬
출력: 위상 정렬의 순서(같은 순서일 경우 아무거나 뽑음)
알고리즘
    1. 모든 정점의 진입 차수를 계산
    2. 진입 차수가 0인 정점을 스택에 삽입
    3. 위상 순서를 생성
"""
adj_mat = [[0, 0, 1, 1, 0, 0],
           [0, 0, 0, 1, 1, 0],
           [0, 0, 0, 1, 0, 1],
           [0, 0, 0, 0, 0, 1],
           [0, 0, 0, 0, 0, 1],
           [0, 0, 0, 0, 0, 0]]


def topological_sort(adj_mat):
    in_degrees = []
    stack = []
    answer = []

    for i in range(len(adj_mat)):
        temp = 0
        for col in range(len(adj_mat)):
            temp += adj_mat[col][i]
        in_degrees.append(temp)

    print("in_degrees: ", in_degrees)

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

    print("stack: ", stack)

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

        for i in range(len(adj_mat[node])):
            if adj_mat[node][i] != 0:
                in_degrees[i] -= 1
                if in_degrees[i] == 0:
                    print("진입차수 0이 된 노드: ", i)
                    stack.append(i)

    print("answer: ", answer)


print(topological_sort(adj_mat))

그럼 아래와 같은 결과를 얻을 수 있다. 

 

답안 2: 인접 리스트 형태의 그래프를 위상 정렬(스택 사용)

"""
인접 행렬에서 본 그래프와 같은 모양의 그래프를 예로 들 것.
입력: 그래프의 인접 리스트
출력: 위상 정렬의 순서(같은 순서일 경우 아무거나 뽑음)
알고리즘
    1. 모든 정점의 진입 차수를 계산
    2. 진입 차수가 0인 정점을 스택에 삽입
    3. 위상 순서를 생성
"""
adj_list = {0: [2, 3], 1: [3, 4], 2: [3, 5], 3: [5], 4: [5], 5: []}


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))

 아래와 같은 결과를 얻을 수 있다.

 

 

답안 3: 인접 리스트 형태의 그래프를 위상 정렬(큐 사용)

"""
이 아래에는 스택이 아닌 큐를 이용해서 위상 정렬을 해보겠다. 
"""

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))

아래와 같은 결과를 얻을 수 있다. 

이해를 돕기 위해  파이썬의 queue라이브러리가 아닌, 리스트를 큐 형태로 사용하였다. 

답안 1의 코드나 답안 2의 코드는, 인풋 형태가 달라짐에 따라 코드가 살짝 달라지는 것을 알 수 있다. 문제에서 주는 인풋에 따라 적절히 손질할 수 있게끔 본인이 연습을 잘 하길 바란다. 

 

답안 2와 답안 3의 코드는, 사용하는 자료구조가 스택인지, 큐인지에 따라 다른 순서가 나오는 것을 의미한다. 여기서 떠오르는 것이, DFS와 BFS가 각각 스택과 큐를 사용했다는 점이다. 이 시점에서 다시 원래 그래프 모양을 보자. 

우리가 지금 위상 정렬하고 있는 그래프인데, 스택을 사용할 경우는 [1, 4, 0, 2, 3, 5], 큐를 사용할 경우는 [0, 1, 2, 4, 3, 5]의 결과가 나온다. 이런 차이점을 바탕으로 우리는 한 가지 더 응용한 결과를 도출할 수가 있다. 

스택을 사용하는 경우는, 우리가 응용문제로 풀어봤던, 가능한 경로를 모두 구하는 것을 생각할 수 있겠다. 이것 말고는 딱히 더 으용할 점이 없어보인다. 

큐를 사용하는 경우는, 같은 위상 순서를 가진 노드를 추출해낼 수 있겠다. 예를 들자면, 아래 코드를 보자. 

응용 1: 인접 리스트 형태의 그래프를 위상 정렬(큐 사용)해서 같은 위상을 가진 정점은 배열로 묶어서 출력하기

adj_list = {0: [2, 3], 1: [3, 4], 2: [3, 5], 3: [5], 4: [5], 5: []}


def queue_topo_sort(adj_list):
    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:
            queue.append(i)

    print("초기 큐: ", queue, "에서 반복 시작")
    while queue:
        print("\nqueue: ", queue)
        answer.append(queue)

        new_arr = []
        for i in queue:
            print(i, "에서 탐색 시작")
            for j in range(len(adj_list[i])):
                idx = adj_list[i][j]
                in_degree[idx] -= 1
                if in_degree[idx] == 0:
                    print("진입차수가 0이 된 정점: ", idx)
                    new_arr.append(idx)

        queue = new_arr

    print("answer: ", answer)


queue_topo_sort(adj_list)

그럼 아래와 같은 결과를 얻는다. 

아까 큐를 사용했을 때와 다른점은, queue에 모든 원소들 각각에 대해서 갈 수 있는 노드들의 진입차수를 1씩 감소시키고, 0이 된 노드들을 new_arr에 추가한 다음, queue에 new_arr을 할당했다. 뭔가 익숙할 것이다. 이것은 BFS응용문제 2번에 해당하는 것처럼 응용한것이다. 

그리고 결과로, answer = [[0, 1], [2, 4], [3], [5]] 가 나왔는데, 이는 무슨의미일까?

바로, 위상 순서대로 정점들을 정렬하되, 같은 위상 순서를 지닌 노드들을 묶어놓은 것이다. 즉, 0,1은 초기에 진입 차수가 0인 정점들이므로, 하나의 배열에 묶어서 answer에 넣어두었다. 그리고, 0과 1이 갈 수 있는 노드들의 진입차수를 1씩 감소시키면, 2번과 4번 노드가 그 다음에 진입 차수가 0이 된다. 그 다음이 3, 그 다음이 5이다. 

한번 더 설명하면, 위상 순서에 따른 같은 순서를 가진 노드들을 배열로 묶어서 보여주고 있는 것이다. 아래 그림을 참조해보자. 

수정된 코드의 answer가 나타내는 값의 의미이다. 기존의 결과인 [0, 1, 2, 4, 3, 5]에서는 0이 1 앞에있기 때문에, 0번 노드와 1번 노드의 위상이 다른지 같은지를 알 수가 없다. 그와 달리 위의 코드의 결과물은 [[0, 1], [2, 4], [3], [5]] 이렇게 같은 위상을 가지는 노드들을 하나의 배열에 묶어줌으로써 기존의 결과물이 갖는 문제점을 해결했다. 

(혹시 위 부분이 이해가 안된다면, 아래 링크로 가서 BFS에 대한 나의 전 게시물 - 응용문제 2번을 구현해보기 바란다.)

2020/03/04 - [공부/알고리즘] - [알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3)

[알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3)

 

 

사실 bfs응용문제 2번을 풀었다면 이게 무슨 소린지 충분히 알 수 있다. 내가 봤을때는, 스택을 이용한 위상 정렬도 응용 가치가 있지만, 큐를 사용해서 같은 위상순서를 지니는 노드를 추출해내는 것이 문제로 나올 가능성이 높지않나~ 하는 아주 개인적인 생각을 해본다. 그러니까 내가 열심히 쓴 이 자료 가지고 열공해서, 하는일 다 잘됐으면 좋겠다.