백준 위상 정렬을 활용해보자
위상 정렬(Topology sort)
위상 정렬은 이론적으로는 사이클이 없는 방향 그래프를 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 즉 위상 정렬은 순서가 정해져있는 작업을 차레로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.
그림 1-1.순서가 정해져있는 작업의 예시
위의 예시를 보면 대학교 입학이후에 두가지의 방향으로 가는 루트가 있다. 그리고 1, 2, 3, 졸업과 같이 앞에 조건을 만족해야하는 순서가 있을 경우에 사용할 수 있는 방법이 위상 정렬이라고 할 수 있다. 그러나 2학년을 마친 후에 군대를 가는 방법도 존재한다는 점을 보면 위상 정렬은 여러가지의 방법이 있다는 점을 알 수 있다.
그림 1-2.사이클이 있는 방향 그래프
추가적으로 위상정렬은 DAG(Direct Acyclic Graph)사이클이 발생하지 않는 방향 그래프에만 적용 가능하다. 위의 예시에서는 취업후에 대학교 입학으로 가는 간선이 생겨서 사이클이 생기므로 위상 정렬을 수행할 수 없다.
그림 2-1.구현하기 위해 숫자로 표현한 사이클이 없는 방향 그래프
구현하기
위상 정렬은 1.그래프가 위상 정렬이 가능한지 2.위상 정렬이 가능할때 결과가 무엇인지이다. 위상 정렬은 큐(Queue)를 이용하여 구현할 수 있다.
진입차수와 진출차수
위상 정렬 알고리즘을 이해하기 위해서는 진입차수와 진출차수에 대해 이해하여야 한다.
- 진입차수(In degree): 특정한 노드로 들어오는 간선의 개수
- 진출차수(Out degree): 특정한 노드에서 나오는 간선의 개수
이를 통해서 각 노드의 진입차수와 진출차수를 정리해보면,
| 정점 | 1번 노드 | 2번 노드 | 3번 노드 | 4번 노드 | 5번 노드 | 6번 노드 | 7번 노드 | 8번 노드 |
|---|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 1 |
| 진출차수 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 0 |
진행 순서
1. 그래프의 시작점을 큐에 넣어주기 위해 진입차수가 0인 노드를 우선적으로 큐에 집어넣는다.
2. 큐에서 원소를 꺼내 연결된 간선을 제거한다. (이때 진입차수와 진출차수도 최신화!)
3. 간선을 제거한 이후에 진입차수가 0이 된 노드를 큐에 넣는다.
4. 큐에 원소가 없을 때까지 2, 3을 순서대로 반복한다.
5. 모든 노드를 방문하기 전에 큐가 비워진다 = 사이클이 존재한다.
모든 노드를 방문후 큐가 비워진다. = 큐에서 꺼낸 순서가 위상 정렬된 순서이다.
그림2-1 풀이
위의 순서를 바탕으로 그림 2-1의 위상 정렬을 하는 방법을 이해해보자.
-
표를 확인했을때 진입차수가 0인 노드는 1번 노드이다. 1번 노드를 큐에 넣어보자
그림 2-2.순서 1 -
이후 그림에서 처럼 1->2간선을 지우면 표가 바뀐다.
정점 1번 노드 2번 노드 3번 노드 4번 노드 5번 노드 6번 노드 7번 노드 8번 노드 진입차수 0 0 1 1 1 2 1 1 진출차수 0 2 1 1 1 1 1 0 -
이때 방문한 노드인 1을 제외한 진입차수가 0인 노드를 큐에 넣는다.
그림 2-2.순서 2 -
다시 표를 갱신하고 진입차수가 0인 노드를 큐에 넣는다.
정점 1번 노드 2번 노드 3번 노드 4번 노드 5번 노드 6번 노드 7번 노드 8번 노드 진입차수 0 0 0 1 1 1 1 1 진출차수 0 0 1 1 1 1 1 0 -
이처럼 큐에 가장 앞에 있는 노드를 빼고 해당 노드에서 출발하는 간선을 모두 지우고 표를 갱신후 진입차수가 0인 노드를 큐에 넣는 것을 반복한다. 이를 진행하면 아래와 같이 된다.
그림 2-2.구현 과정
이를 활용해서 백준 대표적인 위상 정렬 문제인 줄 세우기 문제를 풀어보자!! 위상 정렬에 대해 이해하였다면 구현할 수 있을 것이다. 아니더라도 코드를 확인하고 이해해보자 위상 정렬을 구현하는 방식을 습득할 수 있을 것이다.
[백준] 2252 줄 세우기
문제
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본것이 아니고, 일부 학생들의 키만을 비교해 보았다.
입력
첫쨰 줄에 N $(1 <= N <= 32,000)$ , M $(1 <= M <= 100,000)$ 이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.
출력
첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러가지인 경우에는 아무거나 출력한다.
코드
import java.util.*;
class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
//입력 받기
int n, m;
n = sc.nextInt();
m = sc.nextInt();
int[] graph = new int[n + 1];
ArrayList<Integer>[] trunk = new ArrayList[n + 1];
for(int i = 0; i <= n ;i++)
trunk[i] = new ArrayList<Integer>();
for(int i = 0; i < m; i++){
int a = sc.nextInt();
int b = sc.nextInt();
graph[b]++; //진입차수 기록을 위한 배열
trunk[a].add(b); //간선 A > B를 ArrayList를 활용해서 기록
}
// 위상 정렬
Queue<Integer> q = new LinkedList<>();
for(int i = 1; i <= n; i++){
if(graph[i] == 0)
q.add(i); //시작점(진입차수가 0인 노드)
}
while(!q.isEmpty()){
int st_node = q.poll(); //큐에서 꺼냄과 동시에 pop();
System.out.print(st_node + " "); //큐에서 나온 노드는 위성 정렬된 노드
for(int i = 0; i < trunk[st_node].size(); i++){
int next_node = trunk[st_node].get(i);
graph[next_node]--; //큐에서 나온 노드와 연결된 간선 제거
if(graph[next_node] == 0){ //갱신된 표에서 진입차수가 0인 노드 찾아서 큐에 넣기
q.add(next_node);
}
}
}
sc.close();
}
}
백준 1311번 할 일 정하기 풀러가기
댓글남기기