위상정렬 알고리즘

위상정렬이란?

필요성

위상정렬(Topological Sort)은 “선행 조건(의존성)이 있는 작업들을, 그 조건을 절대 위반하지 않도록 순서를 정렬”하는 알고리즘입니다.

 

현실의 작업/시스템은 단순 직렬이 아니라 “A를 해야 B 가능”, “B와 C를 끝내야 D 가능”처럼 얽힌 의존성을 가집니다. 이때 임의 순서로 실행하면 다음 문제가 생깁니다. 빌드 실패(의존 모듈이 먼저 준비되지 않음), DB 마이그레이션 오류(FK 제약으로 생성/삭제 순서가 틀림),파이프라인 단계 오류(테스트 전 배포 같은 순서 역전)

 

위상정렬은 이런 의존성을 “방향 그래프”로 모델링한 뒤, 간선 방향(선행→후행)을 지키는 실행 순서를 자동으로 산출합니다.

 

위상정렬의 특징

방향 그래프에서만 의미가 있습니다.

간선 u → v 는 “u가 끝나야 v를 할 수 있다”를 뜻합니다.

DAG(사이클 없는 방향 그래프)에서만 위상정렬이 가능합니다.

사이클이 있으면(순환 의존성) 어떤 순서도 조건을 만족할 수 없습니다.

정답(정렬 결과)은 유일하지 않을 수 있습니다.

동시에 가능한 작업(진입차수 0)이 여러 개면, 그들 간의 상대적 순서는 여러 가지가 가능합니다.

위상정렬을 수행했는데 결과에 모든 노드가 포함되지 않으면, 그래프에 사이클이 존재합니다. 이를 통해 사이클 검출이 가능합니다.

 

활용 사례

• 빌드/컴파일 순서 결정(모듈 의존성)
• 패키지 설치 순서(npm/pip의 dependency resolution)
• DB 마이그레이션(테이블/제약조건 생성·삭제 순서)
• CI/CD 파이프라인(테스트→빌드→배포)
• 선수과목/프로젝트 태스크 의존성 스케줄링
• DAG DP(그래프 DP에서 계산 순서 확보)

 

위상정렬의 원리(Kahn)

 

진입차수

진입차수(in-degree)는 “해당 노드로 들어오는 간선의 개수”입니다.

진입차수 = “이 작업을 시작하기 전에 반드시 완료되어야 하는 선행 작업 수”

 

A → C, B → C 이면

indegree[C] = 2 (C는 A와 B가 끝나야 가능)

 

동작 과정

Kahn 알고리즘은 “지금 당장 가능한 작업(진입차수 0)”부터 처리하면서 그래프를 줄여나갑니다.

1. 모든 노드의 진입차수를 계산
2. 진입차수 0인 노드를 큐에 넣기
3. 큐가 빌 때까지 반복

• 큐에서 노드 u를 꺼내 결과에 추가
• u에서 나가는 간선(u → v)을 제거한다고 생각하고 indegree[v]--
• indegree[v]가 0이 되면 v를 큐에 삽입

결과에 포함된 노드 수가 N이면 성공, N보다 적으면 사이클 존재

 

중요 포인트:

• 큐에 들어가는 순간은 “선행 조건이 모두 충족된 순간”
• 큐에서 꺼내는 순간은 “그 노드를 실행(확정)하는 순간”

 

코드로 구현( 백준 문제 1516번)

https://www.acmicpc.net/problem/1516

문제 분석

• 문제 핵심: 각 건물 i를 짓는 데 시간 time[i]가 걸리고, 어떤 건물은 다른 건물들이 먼저 완성되어야 시작할 수 있습니다.
• 즉 “선행 건물 → 후행 건물” 형태의 의존성이 있으며, 전체는 방향 그래프로 표현됩니다.
• 목표: 각 건물 i가 “완성되는 최소 시간”을 구하는 것.

왜 위상정렬을 써야 하나:

• 의존성(선행 조건)이 있는 작업들을 “가능한 순서”로 처리해야 합니다. (위상정렬의 필요성)
• 사이클이 없다는 전제 하에서(일반적으로 건설 의존성은 순환을 허용하지 않음) DAG가 되고, 위상정렬로 선행부터 처리할 수 있습니다.
• 단순히 순서만 구하는 게 아니라, “최소 완료 시간”이라는 DP 값을 누적해야 합니다.
• 각 건물 i의 완료 시간은:
  • i의 모든 선행 건물들이 끝나는 시간 중 최댓값 + time[i]
  • 즉, 선행이 여러 개면 “가장 늦게 끝나는 선행”을 기다려야 하므로 max를 취합니다.

정의:

• dp[i] = i 건물이 완성되는 최소 시간(최종 답)
• dp[i] = time[i] + max(dp[p]) for all prerequisites p of i( i번 건물의 완성 시간 =
  자기 건설 시간 + 선행 건물들 중 가장 늦게 끝나는 시간)

위상정렬 순서대로 처리하면, i를 계산할 때 필요한 선행 p들의 dp가 이미 계산되어 있습니다.

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector<vector<int>> arr(n + 1);      // 위상정렬용 그래프(인접 리스트): u -> v (u가 선행, v가 후행)
	vector<int> timeCost(n + 1);         // 각 노드(건물)의 자체 건설 시간
	vector<int> indegree(n + 1);         // 진입차수: 아직 남아있는 "선행 조건" 개수
	vector<int> answer(n + 1, 0);        // dp(누적): 해당 건물을 시작하기 전까지 필요한 "최대 선행 완료 시간"
	queue<int> q;                        // Kahn 알고리즘 큐: 진입차수 0(즉시 시작 가능)인 노드들

	for (int i = 1; i <= n; i++) {
		cin >> timeCost[i];
		while (true) {
			int a;
			cin >> a;
			if (a != -1) {
				arr[a].push_back(i);     // 간선 a -> i 추가 (a를 먼저 지어야 i를 지을 수 있음)
				indegree[i]++;           // i의 선행 조건이 하나 늘어났으므로 진입차수 증가
			}
			else {
				break;
			}
		}
	}

	// 진입차수 0인 노드는 선행 조건이 없으므로 "위상정렬의 시작점"이 됨
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}

	// Kahn 위상정렬 진행: 큐에서 "현재 시작 가능한" 노드를 꺼내고, 그 영향(간선 제거)을 전파
	while (!q.empty()) {
		int data = q.front(); // data: 현재 선행 조건이 모두 충족된 노드(처리/확정 가능한 노드)
		q.pop();

		// data를 선행으로 가지는 후행 노드들(next)을 갱신
		for (int next : arr[data]) {

			indegree[next]--;  // data를 처리했으므로 next의 선행 조건 하나가 충족됨(간선 제거 효과)

			// dp 갱신:
			// next는 여러 선행 노드를 기다릴 수 있으므로,
			// "선행들 중 가장 늦게 끝나는 시간"을 유지해야 함
			// answer[next] = max(answer[next], 완료시간(data))
			// 완료시간(data) = answer[data] + timeCost[data]
			answer[next] = max(answer[next], answer[data] + timeCost[data]);

			// next의 선행 조건이 모두 사라졌으면(진입차수 0),
			// 이제 next도 위상정렬 큐에 들어가 처리 가능
			if (indegree[next] == 0) {
				q.push(next);
			}
		}
	}

	// 최종 완성 시간:
	// dp(선행 중 최대 완료시간) + 자기 건설 시간
	for (int i = 1; i <= n; i++) {
		cout << answer[i] + timeCost[i] << "\n";
	}

	return 0;
}