안녕하세요 이번 시간에는 위상 정렬 문제를 분석해보는 시간을 갖도록 하겠습니다. 먼저 위상 정렬이란, 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다. 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용되며 사이클이 없어야 하고 항상 유일한 값으로 정렬되지 않아도 되는 경우에만 사용할 수 있습니다. 시간복잡도는 O(노드 수 + 간선 수)를 가져 특정 경우에서 빠른 속도를 얻을 수 있습니다.
위상 정렬의 순서는 다음과 같습니다.
1. 각 노드가 연결된 그래프(인접 리스트)와 각 노드를 향하는 노드의 개수를 담은 배열(진입 차수 배열)이 필요합니다.
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정답 큐에 저장합니다.
3. 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼준 후 뺀 후의 진입 차수 배열이 0인 경우 정답 큐에 다시 추가합니다.
위상 정렬 구현을 백준 2252(줄 세우기) 문제를 통해 구현해보겠습니다. 일부 학생들의 키를 두 명씩 비교한 결과가 주어졌을 때 줄을 세우는 프로그램을 작성하는 문제로 비교할 자료가 일부 존재하기 때문에 주어진 학생들의 연관관계를 그래프로 하여 위상 정렬을 진행합니다. 여기서 주의할 점은 그래프 생성 시 양방향 그래프가 아닌 단방향 그래프로 생성해야 정상적으로 실행됩니다.
import java.util.*;
import java.io.*;
class Main{
static int N,M;
static List<Integer>[] graph;
static int[] map;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new List[N+1];
map = new int[N+1];
for(int i=1;i<=N;i++) graph[i] = new ArrayList<>();
for(int i=0;i<M;i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a].add(b);
map[b]++;
}
Queue<Integer> queue = new ArrayDeque<>();
for(int i=1;i<=N;i++){
if(map[i]==0) queue.add(i);
}
StringBuilder sb = new StringBuilder();
while(!queue.isEmpty()){
int curr = queue.poll();
sb.append(curr).append(" ");
for(int next : graph[curr]){
map[next]--;
if(map[next]==0) queue.add(next);
}
}
System.out.println(sb);
}
}위상 정렬 문제는 사이클이 없는 연결된 그래프를 활용한 최대 최소 문제에서 많이 사용됩니다. DP를 사용해야 할 느낌의 문제 중 그래프를 이용한 문제에서 많이 사용됩니다.
백준 1516(게임 개발) 문제의 경우 모든 건물이 완성되기까지 걸리는 최소 시간을 출력하는 문제입니다. 위상 정렬을 이용하여 각 건물이 생성되기까지 필요한 이전 건물 생성 시간의 최소 시간을 구하면 됩니다. 이전 건물의 생성 시간의 최소 시간은 Math.max(현재 건물 생성 최소 시간, 이전 건물 생성 최소 시간 + 현재 건물 생성 시간)으로 얻을 수 있으며 이렇게 얻은 현재 건물 생성 최소 시간에 현재 건물 생성 시간을 더해 정답을 출력합니다.
백준 1958(임계 경로) 문제의 경우 시작 도시부터 도착 도시까지 출발하여 가능한 모든 경로를 탐색 시 마지막에 도착하는 사람까지 도착하는 시간과 달려야 하는 도로의 수를 구하는 문제입니다. 문제를 다르게 해석하면 그래프의 시작점과 출발점까지의 가장 먼 경로를 이동하는데 걸리는 시간과 거쳐간 노드의 수를 구하는 문제로 볼 수 있습니다. 가장 먼 경로 이동 시간의 경우 시작점과 출발점을 기준으로 위상 정렬을 진행하며 배열의 시작 지점에서 도착 지점까지 갈 수 있는 경로의 최솟값을 저장하는 방식으로 구할 수 있습니다. 거쳐간 노드 수는 에지 뒤집기, 즉 역방향 인접 리스트로 도착 지점에서 시작 지점으로 위상 정렬을 진행하면서 다음 노드의 경로의 최솟값과 간선의 값의 합이 현재 경로 최솟값과 같을 경우 카운트를 증가시키는 방식으로 풀 수 있습니다. 여기서 주의할 점은 시작점에서 출발하기 때문에 진입 차수 배열이 0인 값을 큐에 넣는 것이 아닌 시작 위치만 넣는다는 것입니다.
