[위상정렬] SWEA 1267 작업순서

SH·2025년 9월 14일

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN&categoryId=AV18TrIqIwUCFAZN&categoryType=CODE&problemTitle=%EC%9E%91%EC%97%85&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

문제접근

주어진 방향 그래프에서 순서를 찾는 문제이다. 한 작업이 끝나야 다른 작업을 시작할 수 있다는 의존성에 대한 조건이 존재하며 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph) 형태로 주어져 있다.

SWEA상에서 높은 난이도로 책정되어 있지만 위상정렬 알고리즘에 대해 알고 있으면 쉽게 구현이 가능하다.

위상정렬 알고리즘의 프로세스는 다음과 같다.

1. 정의 :

각 작업을 정점(V)으로, 선행 관계를 간선(E)으로 모델링 한다.

2. 탐색 :

선행 작업이 하나도 없는, 즉시 시작 가능한 작업들을 탐색한다. 그래프 용어로는 진입차수(In-degree)가 0인 정점을 찾는 것

3. 처리 :

진입 차수가 0인 작업을 처리 순서에 추가하고, 그래프에서 이 작업을 제거한다.
이 작업이 제거되면, 이 작업에 의존하던 다른 작업들의 선행 조건이 하나씩 해소된 셈으로 해당 작업들의 진입 차수를 1씩 감소시킨다.

4. 반복 :

위 처리과정에서 새롭게 진입 차수가 0이 된 작업들을 찾아 2번 과정부터 다시 반복한다. 모든 작업이 처리 순서에 추가될 때 까지 이 과정을 반복

이러한 접근 방식은 칸 알고리즘(Kahn's Algorithm)으로 알려져 있으며 BFS와 유사한 방식으로 동작한다.

문제 조건

정점(작업)의 개수 V: 3 ≤ V ≤ 1000
간선(선행 관계)의 개수 E: 2 ≤ E ≤ 3000
그래프 특징: 사이클이 존재하지 않는 방향 그래프 (DAG)
출력: 가능한 여러 작업 순서 중 하나만 출력

문제 설계

자료구조

인접 리스트(List<Integer>[] adjList): 그래프의 연결 관계를 표현한다. adjList[u]는 작업 u가 완료되어야 시작할 수 있는 후속 작업들의 리스트를 저장한다.
진입 차수 배열(int[] inDegree): 각 작업에 대해 필요한 선행 작업 수를 저장한다. inDegree[v]는 작업 v를 시작하기 전에 완료되어야 하는 작업의 개수이다.
큐 (Queue<Integer>): 현재 즉시 수행 가능한 작업들(진입 차수가 0인 정점)을 보관하는 데 사용된다. FIFO(선입선출) 구조가 여러 유효한 순서 중 자연스럽게 하나를 선택하게 해준다.

로직 (칸 알고리즘)

그래프 및 진입 차수 초기화:

V+1 크기의 인접 리스트와 진입 차수 배열을 생성한다. (정점 번호가 1부터 시작하므로)
E개의 간선 정보를 입력받아 u v에 대해, adjList[u]에 v를 추가하고 inDegree[v]의 값을 1 증가시킨다.

초기 큐 설정:

1부터 V까지 모든 정점을 순회하며 inDegree가 0인 정점을 큐에 모두 삽입(offer)한다. 이들이 선행 작업 없이 가장 먼저 시작할 수 있는 작업들이다.

위상 정렬 실행:

큐가 빌 때까지 다음을 반복한다.
- 큐에서 정점 cur를 하나 꺼내(poll) 결과 리스트에 추가한다.
- adjList[cur]를 통해 cur 작업이 끝나야 시작할 수 있는 모든 후속 작업 next를 확인한다.
- 각 next 작업의 진입 차수(inDegree[next])를 1 감소시킨다.
- 만약 inDegree[next]가 0이 되면 next 작업의 모든 선행 작업이 완료되었다는 의미이므로 next를 큐에 삽입한다.

결과 출력:

반복이 끝나면 결과 리스트에 저장된 작업 순서를 형식에 맞게 출력한다. 문제에서 사이클이 없다고 보장했으므로, 모든 정점이 결과에 포함된다.

시간 복잡도

그래프 초기화: 모든 간선 E개를 한 번씩 순회하므로 $O(E)$
초기 큐 설정: 모든 정점 V개를 한 번씩 순회하므로 $O(V)$
정렬 루프: 모든 정점은 정확히 한 번 큐에 들어가고 나오며( $O(V)$ ), 모든 간선은 진입 차수를 감소시키는 데 정확히 한 번 사용된다.( $O(E)$ ).
최종 시간 복잡도: $O(V+E)$

구현 코드

package SWEA.D6;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 작업순서 (위상정렬)
 * V 개 작업 어떤 작업은 특정 작업이 끝나여 시작 가능 -> 선행 관계
 * 
 * 작업과 선행관계 그래프
 * 선행 관계는 방향성을 가진 간선으로 표현
 * 사이클 존재 x
 * 
 * 일을 끝낼 수 있는 작업 순서 찾기
 * 
 * 모든 정점의 진입차수 기록
 * 0부터 단계별 bfs 탐색
 */
public class D6_1267 {
	static int V, E;
	static List<List<Integer>> graph;
	static int[] indegree;
	static int[] result;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int tc = 1; tc <= 10; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			
			indegree = new int[V + 1];
			graph = new ArrayList<>();
			
			// 그래프 초기화
			for (int i = 0; i <= V; i++) {
				graph.add(new ArrayList<>());
			}
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < E; i++) {
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				
				// 그래프 연결 및 진입차수 기록
				graph.get(s).add(e);
				indegree[e]++;
			}
			
			sb = new StringBuilder();
			sb.append("#").append(tc).append(" ");
			
			// 단계별 bfs
			bfs();
			
			
			System.out.println(sb.toString());
			
		}
	}
	
	public static void bfs() {
		ArrayDeque<Integer> queue = new ArrayDeque<>();
		int t = 1;
		// 진입차수가 0개인 노드들을 입력
		for (int i = 1; i <= V; i++) {
			if (indegree[i] == 0) {
				queue.offer(i);
				sb.append(i).append(" ");
			}
		}
		
		while(!queue.isEmpty()) {
			t++;
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int cur = queue.poll();
				
				for (int e: graph.get(cur)) {
					indegree[e]--;
					if (indegree[e] == 0) {
						sb.append(e).append(" ");
						queue.offer(e);
					}
				}
			}
		}
		
	}
}