[BOJ/Topological Sort] 백준 2252 - 줄 세우기 (Java)

2252 - 줄 세우기

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

문제

N명의 학생 키 순서대로 줄 세움
두 학생의 키를 비교하는 방법 사용 (모든 학생 다 비교 X 일부 O)
=> 일부 학생들의 키 비교한 결과 주어졌을 때 줄 세우는 프로그램

입력
첫째 줄: N (1 <= N <= 32,000), M (1 <= M <= 100,000, 키를 비교한 횟수)
다음 M개의 줄: 키를 비교한 두 학생의 번호 A, B (A가 B 앞에 서야 함)
(학생들의 번호 1 ~ N번)
출력: 학생들을 앞에서부터 줄을 세운 결과(답 여러 가지인 경우 아무거나 출력)

---

풀이

위상정렬(Topological Sort)

방향이 있는 비순환 그래프(DAG; Directed Acyclic Graph)에서 모든 간선의 방향 지키며 정점 나열하는 것

• 모든 정점의 진입차수(in-degree) 계산 -> 들어오는 간선 개수
• 진입 차수 0인 노드(= 앞에 올 게 X 노드)를 큐에 삽입
• 큐에서 하나씩 꺼내 결과 리스트에 추가
• 해당 노드가 가리키는 노드의 진입차수 1 감소
• 새롭게 진입차수 0이 되면 큐에 추가
• 큐가 빌 때까지 계속

 

• `graph[a]`: a 학생보다 뒤에 서야 하는 학생들의 리스트 (a -> b 방향 간선 표현)
• `inDegree[b]`: b로 들어오는 간선 = b 앞에 서야 할 사람 수
• ex. 4 2 -> `graph[4].add(2)` / `inDegree[2]++`: 2는 4 뒤에 서야 함

 

• 진입 차수 0 = 아무도 자신 앞에 서지 않아도 되는 학생 -> 줄 맨 앞에 올 수 있음
  -> 큐에 먼저 넣고 하나씩 꺼내며 순서 정함
• BFS 기반 위상 정렬
  • 큐에서 학생 꺼냄 -> 앞에 설 사람 X -> 순서에 추가
  • 그 학생이 가리키는 다음 학생(`next`)의 진입차수 감소
    -> 앞에 서야 할 사람 하나 빠짐
  • IF. 진입차수 0 -> 그 학생도 줄 설 수 있음 -> 큐에 추가

Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= N; i++) {
	// 진입 차수 0
    if (inDegree[i] == 0) q.offer(i);
}

while (!q.isEmpty()) {
    int cur = q.poll();
    sb.append(cur).append(' ');

    for (int next : graph[cur]) {
        inDegree[next]--;
        if (inDegree[next] == 0) q.offer(next);
    }
}

 

---

코드

import java.io.*;
import java.util.*;

// 줄 세우기
public class boj_2252 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Integer>[] 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 < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            graph[A].add(B);
            inDegree[B]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            int cur = q.poll();
            sb.append(cur).append(' ');

            for (int next : graph[cur]) {
                inDegree[next]--;
                if (inDegree[next] == 0) q.offer(next);
            }
        }

        System.out.println(sb);
    }
}