위상정렬이란

• 방향 그래프의 정점들을 간선의 방향을 지켜서 나열하는 것이다.
• 선행 작업을 먼저 수행한 후에 후행 작업을 수행하도록 작업 순서를 정렬하는 알고리즘이다.

따라서, 사이클이 없는 방향 그래프(DAG)에서만 가능하고, 사이클이 있으면 위상정렬이 불가능하다.

(정답 여러개 가능)

위상 정렬로 풀 수 있는 문제 ⭐️

일반 정렬 : 숫자나 문자열처럼 값의 크기를 비교해 정렬
위상 정렬 : 노드 간의 선후 관계를 정렬 “순서 규칙”을 만족하도록 나열한다,

• 위상 정렬에는 선후 관계에 대한 규칙이 있다. (“1번은 2번보다 앞선다.”, “3번은 4번보다 앞선다”...)

따라서, 순서의 규칙이 있는 문제에 적용할 수 있으며, 풀이 과정 중 사이클의 존재를 확인할 수 있다.

문제 구별법

1. 선후관계나 순서정하기
   • "A 작업을 끝내야 B 작업을 시작할 수 있다”
   • 선수 과목, 선행 조건…
   • "A는 B보다 먼저 와야 한다”
   • 가능한 순서 중 하나를 출력
2. 사이클 판별
   • "순서를 정할 수 없는 경우를 판별”

대표적인 유형

• 작업 스케줄링 (선행 작업 있음)
• 커리큘럼 문제 (선수과목)
• 빌드 순서 (의존성 관리)
• 게임 캐릭터 순위 정하기

풀이 방법

키워드 정리

• 진입 차수 : 특정 노드로 들어오는 화살표(간선)의 개수
• 큐 : 진입 차수가 0인 노드들을 처리하기 위한 임시 저장소
• 결과 : 위상 정렬의 결과를 저장하기 위한 리스트

풀이 방법

1. 진입 차수가 0인 노드를 큐에 삽입
   1. 큐에서 노드를 꺼내 결과에 추가
   2. 해당 노드와 연결된 간선을 제거 (연결된 노드의 진입차수 -1)
   3. 진입차수가 0이 된 노드를 큐에 삽입
2. 큐가 빌 때까지 a~c 반복
3. 결과의 크기가 전체 노드 개수와 같지 않으면 사이클 존재

---

실제 문제 풀어보기 : 2252 줄세우기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	68472	41495	27799	58.603%

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

3 2
1 3
2 3

예제 출력 1

1 2 3

내 풀이

정답 코드 (다듬은 버전)

• 문자열 출력에 StringBuilder 사용
• Queue 구현체를 ArrayDeque 선택

실제로 시간이 반절가까이 감소해, 성능 확인

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ2252줄세우기V_2 {
    public static void main(String[] args ) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // StringBuilder: 반복적인 문자열 연결 시 System.out.print()보다 훨씬 빠름
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //그래프 그리기
        List<Integer>[] graph = new ArrayList[n + 1];
        int[] degree = new int[n+1];

        //1부터 n 까지만 초기화, 불필요한 9번 인덱스 초기화 제거
        for(int i = 1; i < n+1; 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);
            degree[b]++;
        }

        //Queue 연산은 LinkedList 보다 ArrayDeque 이 적합
        // add, remove 보다는 offer, poll 권장 ✅
        Queue<Integer> q = new ArrayDeque<>();
        ArrayList<Integer> result = new ArrayList<>();

        //진입차수가 0인 ⭐️!! 조건식을 M으로 해서 문제
        for (int i = 1; i < n+1; i ++){
            if (degree[i] == 0) {
               q.offer(i);
            }
        }

        while(!q.isEmpty()){
            //큐에서 노드를 꺼내 결과에 추가
            // 📌 반복문 외부 선언 vs 내부 선언
            // ✅ 성능은 동일하고, 가독성과 안정성 면에서 내부 선언이 더 우수
            int node = q.poll();
            sb.append(node).append(' ');

            //해당 노드와 연결된 간선을 제거 (연결된 노드의 진입차수 -1)
            for (int k : graph[node] ){
                degree[k]--;
                if (degree[k] == 0){
                    q.add(k);
                }
            }
        }

        System.out.println(sb);

    }
}

실패 코드

• 오타로 인한 실패 ! 😩

        for (int i = 0; i < m; i++) { // 차수 계산하는 부분을 n이 아닌 m번 반복해 인덱스 에러 
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            degree[b]++;
        }

처음 풀이 링크드 리스트로 풀기

1. 비교 정보 리스트 정렬 → 1 2 / 2 4 / 3 2 → 1 2, 2 4, 3 2,
2. 링크드 배열에 값 넣기
   1. 1번의 결과의 첫번째를 배열 첫번째 링크드 배열의 값으로 선언
   2. 1번의 결과의 두번째값을 링크드 배열의 값으로 선언, 이 객체를 첫번째 배열의 next값으로 설정
   3. 그 다음…???
   4. 2번의 결과의 첫번째 값을 세번째 객체로 설정, 두번째 객체의 넥스트 값으로 이 객체 설정

—> 문제 !!

• 2번의 결과의 첫번째 값과, 1번의 결과의 두번째 값이 같은 걸 어떻게 구별할 것인가???*
  

    [1, 2] ⇒ [2, 3] 인 상태에서 
    1. [4, 2]를 넣어야해! 그러면, 2를 원래 가리키던 1를 찾아야하는데
    매번 이 리스트를 전체 순회해서 찾기? (n회 반복)
    2. [2,5]를 넣는다면? 2가 가리키는 3에 3->5를 해야하는데, 2를 value로 하는 애들 찾아야하니까.. 또 n번 순회
    
    한번 넣을때마다, 
    첫번째 요소가 이미 값으로 있는지 체크 (n회), 첫번째 요소를 가리키고 있는 애가 있는지 (n회) 
    --> n*n

이중 for문 → 연산 횟수는 n^2
32,000 ^ 2 ≈ 1,024,000,000
→ 약 10억 번 반복

n이 32,000이고, 시간 제한이 2초 → 무조건 이중 포문은 안된다는 결론이 나온다

n	반복 횟수 n2n^2n2	대략 시간 (빠름 기준 4e8 ops/s)	대략 시간 (느림 기준 2e8 ops/s)
1,000	1,000,000	0.0025초	0.005초
5,000	25,000,000	0.06초	0.12초
10,000	100,000,000	0.25초	0.5초
20,000	400,000,000	1초	2초
32,000	1,024,000,000	2.56초	5.12초

오답노트

⭐️ 결국, 시간 복잡도를 고려하지 않고 대강 풀어서 시간을 버렸다. 어떤 알고리즘을 적용하기 전에는 이거다! 확신을 갖고 풀어야겠다 (시간 복잡도나, 문제의 특징을 바탕으로!)