핵심 요약
- 위상정렬(Topological Sort)은 ‘순서가 정해진 작업’을 차례대로 수행할 때 사용하는 알고리즘입니다.
- 반드시 사이클이 없는 방향 그래프(DAG)에서만 수행할 수 있습니다. (꼬리 물기 금지!)
- 대표적인 해결법은 진입 차수(In-degree)를 이용해 선행 조건이 없는 것부터 처리하는 방식입니다.
- 백준 1005번(ACM Craft) 같은 건설/수강 신청 문제는 위상정렬과 DP(다이나믹 프로그래밍)를 결합해 풉니다.
- 정석은 큐(Queue)를 쓰지만, 역방향 DFS를 활용하면 더 직관적인 코드로 풀 수 있는 꿀팁이 있습니다.
목차
- 1. 위상정렬이란?
- 2. 작동 원리: 줄 세우기의 규칙
- 3. 실전 공략: 백준 1005번 ACM Craft
- 4. 정석 코드 (진입 차수 + 큐)
- 5. 팁: 역발상 DFS로 쉽게 풀기
- 자주 묻는 질문 (FAQ)
코딩 테스트를 준비하다 보면 “선수 과목을 다 들어야 졸업 가능”이라거나 “이 건물을 지어야 다음 건물을 지을 수 있음” 같은 문제들을 마주하게 됩니다. 우리 일상으로 치면 ‘양말을 신어야 신발을 신을 수 있는 것’과 같죠. 이런 순서의 제약이 있는 문제들을 컴퓨터가 가장 빠르고 정확하게 해결하는 방법, 바로 위상정렬(Topological Sort)입니다. 오늘은 복잡해 보이는 알고리즘 용어를 중학생도 이해할 수 있게 풀어드리고, 실제 기출문제까지 완벽하게 정복해 보겠습니다.
1. 위상정렬이란? (게임 스킬 트리로 이해하기)
위상정렬은 이름이 참 어렵지만, 개념은 우리가 게임에서 흔히 보는 ‘스킬 트리(Skill Tree)’와 똑같습니다.
핵심 비유: 게임 스킬 찍기
- 상황: 강력한 궁극기 ‘메테오’를 배우고 싶습니다.
- 조건: 하지만 ‘메테오’를 배우려면 먼저 ‘파이어볼’ 레벨 5를 찍어야 하고, ‘파이어볼’을 배우려면 ‘매직 클로’를 먼저 배워야 합니다.
- 결과: [매직 클로] → [파이어볼] → [메테오] 순서로 배워야 합니다. 이 순서를 정해주는 것이 바로 위상정렬입니다.
이때 가장 중요한 조건이 하나 있습니다. 바로 “사이클(Cycle)이 없어야 한다”는 점입니다. 만약 A를 하려면 B가 필요하고, B를 하려면 C가 필요한데, C를 하려면 다시 A가 필요하다면? 우리는 영원히 아무것도 시작할 수 없게 됩니다. 그래서 위상정렬은 ‘방향은 있되, 뱅글뱅글 도는 구간이 없는 그래프(DAG)’에서만 가능합니다.
2. 작동 원리: 줄 세우기의 규칙
컴퓨터는 이 순서를 어떻게 알아낼까요? 가장 대중적인 방법은 ‘진입 차수(In-degree)’라는 개념을 사용하는 것입니다. 말이 어렵지만, 쉽게 말해 “나를 가리키는 화살표의 개수”, 즉 “내 앞에 남은 숙제의 개수”라고 생각하면 됩니다.
- 1단계: 모든 작업의 ‘진입 차수(선행 조건 개수)’를 셉니다.
- 2단계: 진입 차수가 0인 작업(아무 조건 없이 바로 할 수 있는 일)을 찾아 큐(대기열)에 넣습니다.
- 3단계: 큐에서 작업을 하나 꺼내 수행하고, 그 작업과 연결된 다음 작업들의 진입 차수를 1씩 깎습니다. (숙제 하나 해결!)
- 4단계: 새롭게 진입 차수가 0이 된 작업들을 다시 큐에 넣습니다.
- 5단계: 큐가 빌 때까지 반복합니다.
(진입 차수가 0인 노드부터 제거해 나가는 과정)
3. 실전 공략: 백준 1005번 ACM Craft
이제 이론을 실전에 적용해 봅시다. 백준 1005번 ‘ACM Craft’는 위상정렬의 교과서 같은 문제입니다.
- 문제 상황: 특정 건물(승리 조건)을 짓기 위해 테크트리를 타야 합니다.
- 특징: 각 건물마다 건설 시간(비용)이 다릅니다. 동시에 지을 수 있는 건물의 경우 가장 오래 걸리는 시간을 기다려야 다음 단계로 넘어갈 수 있습니다.
- 핵심 공략: 단순 순서뿐만 아니라, DP(다이나믹 프로그래밍)를 섞어서 “여기까지 오는 데 걸린 최대 시간”을 계산해야 합니다.
4. 정석 코드 (진입 차수 + 큐)
가장 널리 쓰이는 진입 차수(In-degree) 방식의 정석 풀이입니다. 그래프를 정방향(A→B)으로 저장하고, 큐를 사용해 앞에서부터 차근차근 해결해 나갑니다.
import java.util.*;
// [정석 풀이] 위상정렬 (Kahn's Algorithm)
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 테스트 케이스
while (T-- > 0) {
int N = sc.nextInt(); // 건물 개수
int K = sc.nextInt(); // 규칙 개수
int[] time = new int[N + 1]; // 건설 시간
for (int i = 1; i <= N; i++) time[i] = sc.nextInt();
List[] graph = new ArrayList[N + 1]; // 연결 정보
for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
int[] inDegree = new int[N + 1]; // 진입 차수(선행 조건 수)
for (int i = 0; i < K; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph[a].add(b); // a를 지어야 b 가능 (정방향)
inDegree[b]++; // b의 진입 차수 증가
}
int W = sc.nextInt(); // 목표 건물
// 위상 정렬 시작
// result[i]: i번 건물을 짓기까지 걸리는 최소 시간 (DP)
int[] result = new int[N + 1];
Queue q = new LinkedList<>();
for (int i = 1; i <= N; i++) {
result[i] = time[i]; // 초기값은 자기 자신 시간
if (inDegree[i] == 0) q.offer(i); // 조건 없는 건물 큐에 넣기
}
while (!q.isEmpty()) {
int cur = q.poll();
for (int next : graph[cur]) {
// 다음 건물의 완료 시간 갱신
// (이전 건물들 중 가장 늦게 끝나는 시간 + 내 건설 시간)
result[next] = Math.max(result[next], result[cur] + time[next]);
inDegree[next]--; // 선행 조건 하나 해결
if (inDegree[next] == 0) q.offer(next);
}
}
System.out.println(result[W]);
}
}
}
5. 팁: 역발상 DFS로 쉽게 풀기
위의 정석 풀이도 훌륭하지만, 관점을 조금만 바꾸면 훨씬 직관적인 코드를 짤 수도 있습니다.
"건물을 짓고 나서 뭘 지을까?" (정방향) 대신
"이걸 지으려면 뭐가 필요하지?" (역방향) 로 생각해보세요.
이 방식은 재귀 함수(DFS) + 메모이제이션(DP)을 활용합니다. 목표 건물에서 시작해 필요한 재료(이전 건물)들을 파고 들어가는 방식이라, 불필요한 건물은 계산하지 않아도 된다는 장점이 있습니다.
import java.util.*;
class Main {
static int n, m, k;
static int[] time; // 각 건물당 건설 시간
static List[] tree; // 건물 간의 연결 관계 (역방향 그래프)
static int[] dp; // 메모이제이션 배열 (이미 계산한 값 저장)
// k번 건물을 짓는 데 걸리는 총 시간을 구하는 함수 (DFS 재귀)
static int dfs(int k) {
// 1. 메모이제이션 (Memoization) 핵심!
// 만약 dp[k]가 -1이 아니라면, 이미 계산해둔 값이므로 다시 계산하지 않고 바로 리턴합니다.
// 이 한 줄이 시간 복잡도를 획기적으로 줄여줍니다.
if (dp[k] != -1) return dp[k];
// 2. 현재 건물을 짓는 시간은 무조건 포함됩니다.
// 잠시 임시 변수(t)를 이용해 이전에 지어야 할 건물들 중 가장 오래 걸리는 시간을 찾습니다.
int maxPrevTime = 0;
// 3. k번 건물을 짓기 위해 필요한 '재료 건물(child)'들을 모두 확인합니다.
for (int child : tree[k]) {
// 필요한 건물들 중, 완성까지 가장 오래 걸리는 시간을 찾습니다.
// 동시에 지을 수 있기 때문에 '합(Sum)'이 아니라 '최대값(Max)'을 구해야 합니다.
maxPrevTime = Math.max(maxPrevTime, dfs(child));
}
// 4. (가장 늦게 끝나는 선행 건물 시간) + (내 건설 시간)을 dp에 저장하고 반환합니다.
dp[k] = time[k] + maxPrevTime;
return dp[k];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 테스트 케이스 개수
for (int X = 0; X < T; X++) {
n = sc.nextInt(); // 건물의 개수
m = sc.nextInt(); // 건설 순서 규칙의 개수
// 인덱스를 1부터 쓰기 위해 n+1 크기로 생성
time = new int[n + 1];
tree = new ArrayList[n + 1];
dp = new int[n + 1];
// 초기화 과정
for (int i = 1; i <= n; i++) {
tree[i] = new ArrayList<>(); // 그래프 리스트 초기화
dp[i] = -1; // -1은 '아직 방문하지 않음(계산 안 함)'을 의미
time[i] = sc.nextInt(); // 각 건물의 건설 시간 입력
}
// 건설 규칙 입력 (여기가 핵심!)
for (int i = 0; i < m; i++) {
int a = sc.nextInt(); // 먼저 지어야 하는 건물
int b = sc.nextInt(); // 나중에 짓는 건물
// [중요] 역방향 그래프 구성
// "a를 짓고 b를 짓는다" -> "b를 짓기 위해선 a가 필요하다"로 저장
// 이렇게 해야 목표(Target)에서 재료(Source)를 찾아 내려갈 수 있습니다.
tree[b].add(a);
}
k = sc.nextInt(); // 승리하기 위해 지어야 하는 목표 건물
// 목표 건물(k)부터 시작해 필요한 시간을 역추적합니다.
System.out.println(dfs(k));
}
}
}
이 코드는 "목표(Target)를 위해 무엇이 필요한가?"라는 사고방식과 일치하여, 입문자가 로직을 설계할 때 훨씬 직관적으로 다가옵니다. 특히 1005번처럼 특정 목표 하나의 값만 구하면 될 때 아주 강력합니다.
자주 묻는 질문 (FAQ)
Q: 위상정렬은 꼭 DAG(사이클 없는 그래프)여야 하나요?
A: 네, 필수입니다. 사이클이 있다는 건 '닭이 먼저냐 달걀이 먼저냐'처럼 끝이 없는 논쟁에 빠지는 것과 같습니다. 순서를 정할 수 없으므로 위상정렬 알고리즘을 사용할 수 없습니다.
Q: 정석 코드(큐)와 팁 코드(DFS) 중 뭘 써야 하나요?
A: 전체적인 순서가 필요하다면 '정석 코드(큐)'가 좋습니다. 하지만 1005번 문제처럼 특정 목표까지의 누적 값(최대 시간 등)을 구해야 한다면 'DFS + 메모이제이션' 방식이 구현하기 더 빠르고 실수할 확률이 줄어듭니다.