위상 정렬

➊ 배경

나는 1번부터 4번까지 풀어야 하는 문제가 있다.
문제를 푸는 순서에 아래의 제약이 있다고 가정해보자!

• 2번 → 3번
• 4번 → 1번

그렇다면 위의 제약 조건을 만족하면서 문제를 푸는 순서를 어떻게 정할 수 있을까? 🤔

• 4번 → 1번 → 2번 → 3번
• 2번 → 4번 → 1번 → 3번
• 2번 → 3번 → 4번 → 1번

등의 여러가지 경우의 수가 존재한다!

지금은 고작 4개의 문제지만, 문제의 수가 100개 혹은 1000개라면?
사람의 머리로는 답을 찾는 데 오랜 시간이 걸릴 것이다.

따라서 이를 프로그래밍으로 구현하고자 한다.

특정한 조건을 만족하며 노드들을 순서대로 정렬하고자 할 때
우리는 위상 정렬을 이용하여 문제를 해결할 수 있다!

➋ 위상 정렬

그렇다면 위상 정렬.. 그거 어떻게 하는 걸까?

① 그래프화

먼저 위 문제는 그래프로 다시 정의할 수 있다.

1번 문제 풀기, 2번 문제 풀기 등 각각의 작업이 하나의 노드가 될 것이고

• 2번 → 3번
• 4번 → 1번

위의 조건들은,
2번 노드로부터 3번 노드를 단방향으로 잇는 간선,
4번 노드로부터 1번 노드를 단방향으로 잇는 간선으로 정의할 수 있다.

즉 그림으로 표현하면 다음과 같다.

이처럼 문제를 푸는 순서, 관계를 그래프로서 정의한다.

작업의 순서를 그래프로 정의하는 과정부터 시작하여 위상 정렬을 진행한다.

② 진입 차수가 0인 노드를 큐에 삽입

여기서 진입 차수라는 개념이 등장한다.
진입 차수란 한 노드로 들어오는 간선을 의미한다.
위 그림의 노드 1 입장에서 진입 차수는 1이다.
왜냐하면 노드 4가 노드 1을 바라보는 간선이 존재하기 때문이다!

진입 차수가 0인 노드는 노드 4, 노드2이다!
진입 차수가 0인 노드는 자신보다 먼저 실행되어야 할 노드가 없기 때문에
바로 당장 작업을 시작해도 된다!

🚨 그렇기 때문에 선입선출 구조인 큐에 이 노드들을 삽입한다!
이 큐는 현재 작업 중인 노드들이 존재하는 공간이라고 생각하면 된다.

③ 큐에서 제거

큐에 진입 차수가 0인 노드들을 모두 삽입하였으면
이제, 하나씩 다시 꺼낸다.
노드를 큐에서 꺼낸다는 것은 작업이 완료되었다는 뜻이다.

꺼낸 노드와 연결되어 있는 노드는 진입 차수를 -1 감소시켜준다.
즉, 아래와 같은 그림이 된다.

4번 노드의 작업이 완료되었으므로 1번 노드 작업은 이제 먼저 선행되어야 할 작업이 사라진 셈이다.
즉 진입 차수가 0이 되었고 당장 실행 가능하기에 큐에 삽입할 수 있다.

이처럼 ② - ③ 과정을 큐가 빌 때까지 반복한다!

• 진입 차수가 0인 노드를 큐에 삽입
• 큐에서 제거
• 큐에서 제거된 노드와 연결된 노드의 진입 차수 -1 감소

큐에서 꺼낸 노드들의 순서가 곧 우리가 문제에서 구하고자 하는 답이다!

위상 정렬은 위와 같은 과정으로 이루어지며
특정 조건을 만족하는 작업들의 순서를 결정하는데 유용하다!

🚨 하지만 그래프가 사이클을 그리게 되면 위상 정렬은 사용할 수 없다!

왜냐하면 2번 노드는 영원히 진입 차수가 0이 될 수 없기 때문이다.
따라서 큐에 들어가지 못하기 때문에 위 노드들의 순서는 결정할 수 없다.