위상 정렬
작업을 수행할 때, 일부 주어진 순서를 따라 작업을 수행하도록 할 수 있다.
(사이클이 없는) 방향 그래프를 따라, 거스르지 않고, 노드를 나열하는 것.
아래 사진을 위상 정렬하면 [1, 2, 3, 4, 5, 6], [1, 2, 5, 3, 4, 6], [1, 2, 5, 6, 3, 4] 등 다양한 경우가 존재할 수 있다.
[예시1]
집을 청소하기 위해서는 다음과 같은 순서를 따라야 한다. 각 작업에 번호를 부여하여 하나의 노드로 바라보면 방향 그래프인 것을 알 수 있다. 쓰레기를 버리려면 그보다 먼저 청소기를 비워야한다. 청소기를 비우기 위해서는 바닥 청소를 해야하고, 바닥 청소를 하기 위해서는 우선 일어나야 한다. 사이사이 다른 할일을 수행할 수도 있다. 예를 들어 일어난 다음 세탁기를 돌리고 바닥 청소를 한 뒤 ~ 쓰레기를 버리고, 빨래를 널거나. 일어난 다음 세탁기를 돌리고 SNS를 하고 바닥 청소를 할 수도 있다. SNS는 누워서도 일어나서도 할 수 있기 때문에 작업의 순서에 상관없이 할 수 있는 것이다.
[예시2]
만약 바닥이 너무 더러워 빨래건조대를 놓을 곳조차 없어서, 빨래를 널기 전에 바닥 청소를 해야한다고 하자. 하나의 작업을 하기 전에 두 개 이상의 작업이 필수적인 경우에도, 위상 정렬로 순서를 나타낼 수 있다.
위상 정렬의 메커니즘은 다음과 같다.
1. 자신을 가리키는 edge가(=indegree가) 없는 노드를 찾아 대기열에 추가한다.
2. 대기열에서 하나의 노드를 꺼내, 출력하고 그 노드가 가리키는 edge를 모두 삭제한다.
3. 대기열에 노드가 남아있다면 1로 돌아간다. (2번에서 edge를 삭제하면서, 자신을 가리키는 edge가 없도록 update된 노드가 있을 수 있기 때문)
/*
/ N : 노드의 개수
/ que : 대기열
/ indegree[i] : i번째 노드의 indegree 수
*/
queue<int> que;
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) { // 1. 자신을 가리키는 edge가(=indegree가) 없는 노드를 찾아 대기열에 추가한다.
que.push(i);
}
}
while (!que.empty()) {
int node = que.front(); // 2-1. 대기열에서 하나의 노드를 꺼내,
que.pop();
cout << node << " "; // 2-2. 출력하고
for (int i = 0; i < connect[node].size(); i++) { // 2-3. 그 노드가 가리키는 edge를 모두 삭제한다.
if (--indegree[connect[node][i]] == 0) { // 3. update 되어 1번을 수행하고 2-1부터 다시 시작한다.
que.push(connect[node][i]);
}
}
}예제
작업 순서에 맞춰 정렬하기
N명의 학생들을 키 순서대로 줄을 세우려고 한다.
각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다.
그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.위상정렬의 기본 개념을 이용하여 풀 수 있는 문제이다.
cin >> N >> M;
int a, b;
for (int i = 0; i < M; i++) {
cin >> a >> b;
connect[a].push_back(b);
++indegree[b];
}
queue<int> que;
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
while (!que.empty()) {
int node = que.front();
que.pop();
cout << node << " ";
for (int i = 0; i < connect[node].size(); i++) {
if (--indegree[connect[node][i]] == 0) {
que.push(connect[node][i]);
}
}
}(응용) 사이클이 있는지 없는지 판단하기
인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는
자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다.
순서를 정하기 위해서는 많은 조건을 따져야 한다.
그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게
각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.
1 4 3
6 2 5 4
2 3
첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다.
두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다.
한 가수를 여러 보조 PD가 담당할 수도 있다. 마지막으로, 세 번째 보조 PD는 2번 먼저, 다음에 3번으로 정했다.
남일이가 할 일은 이 순서들을 모아서 전체 가수의 순서를 정하는 것이다.
남일이는 잠시 생각을 하더니 6 2 1 5 4 3으로 순서를 정했다.
이렇게 가수 순서를 정하면 세 보조 PD가 정해온 순서를 모두 만족한다. 물론, 1 6 2 5 4 3으로 전체 순서를 정해도 괜찮다.
경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다.
예를 들어, 세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다.
이번에 남일이는 우리 나라의 월드컵 4강 진출 기념 음악제의 PD를 맡게 되었는데, 출연 가수가 아주 많다.
이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다.
보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수의 순서를 정하는 프로그램을 작성하시오.- 위 예제와 같이 위상정렬로 다음 문제를 풀 수 있다. 하지만 위 문제와 다른 점은 순서에 해당되는 정렬 결과가 존재하지 않을 수도 있다는 것이다. 문제 설명의 불가능한 예시를 그래프로 표현해보자.
(1번 : 1 -> 4 -> 3
2번 : 6 -> 2 -> 5 -> 4
3번 : 3 -> 2)
- 그래프에 사이클이 존재한다는 것을 알 수 있다. 즉, 위상정렬은 사이클이 존재하는 단방향 그래프에서 제대로 동작하지 않는다!
- 위상정렬은 말 그대로 정렬, 노드를 모두 방문하기 때문에 노드가 대기열에 들어오는 횟수는 노드의 수이다. 따라서 노드의 수만큼 대기열 확인이 일어나지 않으면 사이클이 존재하여 위상정렬로 풀 수 없다는 뜻이 된다! 코드로 표현하면 다음과 같다. 위 코드가 while -> 카운트로 한정된 for문으로 바뀌고, 대기열이 비었는지 확인하는 부분이 추가되었다.
for (int j = 0; j < N; j++) {
if (que.empty()) { // cycle 존재한다는것.
break;
}
int node = que.front();
que.pop();
ans.push_back(node);
for (int i = 0; i < connect[node].size(); i++) {
if (--indegree[connect[node][i]] == 0) {
que.push(connect[node][i]);
}
}
}