(Java) 위상정렬 (feat. 백준 2252 줄 세우기)

위상정렬

위상정렬은 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)에서 순서를 정렬하는 알고리즘이다.

 

위상정렬을 구현하기 위해서는 4가지 변수를 만들어줘야 한다.

• int[] indegree : 특정 노드에 대해서 다른 노드로부터 들어오는 간선의 개수
• List<List<Integer>> array : 그래프의 간선 정보를 담은 2차원 리스트
• Queue<Integer> q : indegree 값이 0이 된 노드들을 담기 위한 queue
• Queue<Integer> result : 정렬된 순서를 보여줄 결과 queue. q에서 빠져나온 순서대로 정렬된다.

 

1. 맨 처음 indegree 값이 0인 노드들을 Queue에 담고 시작한다.

 

2. Queue에서 노드 1을 빼주며 1에서 가르킨 노드들의 indegree 값을 1씩 감소시킨다.

즉, 노드 1부터 시작하는 간선을 지워준다.

그 다음 1 노드를 Result에 추가해준다.

그리고 2와 3 노드가 새롭게 indegree가 0이 됐으므로 Queue에 2, 3을 추가해준다.

 

3. Queue에서 노드 2를 빼주며 2에서 가르킨 노드 4의 indegree 값을 1 감소시킨다.

그 다음 2 노드를 Result에 추가해준다.

그리고 4 노드의 indegree가 0이 됐으므로 Queue에 4를 추가해준다.

 

4. Queue에서 노드 3를 빼주며 3에서 가르킨 노드 5의 indegree 값을 1 감소시킨다.

그 다음 3 노드를 Result에 추가해준다.

그리고 5 노드의 indegree가 0이 됐으므로 Queue에 5를 추가해준다.

 

5. Queue에서 노드 4를 빼주며 4에서 가르킨 노드 6, 7의 indegree 값을 1 감소시킨다.

그 다음 4 노드를 Result에 추가해준다.

 

6. Queue에서 노드 5를 빼주며 5에서 가르킨 노드 6의 indegree 값을 1 감소시킨다.

그 다음 5 노드를 Result에 추가해준다.

그리고 6 노드의 indegree가 0이 됐으므로 Queue에 6를 추가해준다.

 

7. Queue에서 노드 6를 빼주며 6에서 가르킨 노드 7의 indegree 값을 1 감소시킨다.

그 다음 6 노드를 Result에 추가해준다.

그리고 7 노드의 indegree가 0이 됐으므로 Queue에 7를 추가해준다.

 

8. 7 노드를 Result에 추가해준다.

 

 

최종적으로 Queue는 비워지고 Result에 들어간 순서가 위상 정렬된 결과값이다.

위상 정렬은 어려가지 결과값이 존재할 수 있다.

하지만 화살표가 가르키는 순서는 지켜져야 한다.

 

 

위상정렬 알고리즘을 이용하여 문제를 풀어보겠다.

 

 

백준 2252 줄 세우기

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

 

N명의 학생들을 키 순으로 정렬하고자 한다.

입력 조건으로 두 명간의 키를 비교한 결과값만 주어진다.

M 번 키를 비교하는데 두 학생 A, B의 번호가 주어진다.

이는 A가 B의 앞에 서야한다는 의미이다.

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   // 학생 수
        int M = Integer.parseInt(st.nextToken());   // 키를 비교한 횟수

        List<Integer> BArr[] = new ArrayList[N+1];  // 간선 정보 담은 배열 + 리스트
        for(int i = 0; i <= N; i++) {
            BArr[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());

            BArr[A].add(B);
            indegree[B]++;
        }

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

        while(!q.isEmpty()){
            int node = q.poll();
            result.add(node);
            for(int i = 0; i < BArr[node].size(); i++) {
                int tmp = BArr[node].get(i);
                indegree[tmp]--;
                if(indegree[tmp] == 0) {
                    q.add(tmp);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while(!result.isEmpty()) {
            int tmp = result.poll();
            sb.append(tmp + " ");
        }

        System.out.println(sb);
    }
}