백준 2252번 : 줄 세우기 java

이 문제는 위상 정렬을 이용하여 그래프를 일차원으로 나타내는 문제입니다.

위상 정렬에 대하여 우선 설명드리겠습니다.

위상 정렬이란 그래프 내에서 순환이 없을 때 순서에 맞게끔 나열하여 한 줄로 그래프 내에 있는 자료들을 정렬하는
것을 의미합니다.

예를 들어 위와 같은 그래프가 있다고 하겠습니다.

이 그래프를 순서에 맞게 정렬해보도록 하겠습니다.

우선 첫 번째 자리에는 자신을 가리키는 노드가 없는 노드가 들어갑니다.

따라서 1과 6을 큐에 삽입해줍니다.

우선 큐에 먼저 삽입된 1번 노드를 먼저 확인하겠습니다.

1번 노드에서 나아간 간선들을 2와 3을 가리키고 있습니다.

또한 2와 3을 가리키는 다른 노드들이 없기 때문에 큐에 2와 3 노드를 삽입해줍니다.

이제 1과 연결된 다른 노드가 없기 때문에 큐의 맨 앞에 있는 6번 노드를 확인하겠습니다.

이제 6번 노드와 연결되어 있는 노드들을 확인하겠습니다.

6번 노드에서 뻗어나간 간선들은 4와 5번 노드를 가리키고 있습니다.

하지만 4번 노드는 2번 노드도 가리키고 있기 때문에 우선 큐에 넣지 않습니다.

이제 큐에 들어간 다음 노드를 확인하겠습니다.

2번 노드에서 뻗어나간 간선은 4를 가리키고 있습니다.

4번은 6번 노드에서 온 간선도 있었지만 아까 먼저 확인을 해주었습니다.

이제 4번 노드에 온 간선은 2번 노드의 간선 밖에 없기 때문에 4번 노드도 큐에 넣어줍니다.

이제 남아있는 노드가 없기 때문에 큐에 있는 노드들은 배열로 옮겨줍니다.

그럼 위와 같은 배열이 완성되었습니다.

이렇게 정해진 순서대로 그래프를 배열로 만들어 정렬하는 방식을 위상 정렬이라고 합니다.

이제 이 알고리즘을 이용하여 이 문제를 해결하는 모습을 보여드리겠습니다.

---

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

public class Main {
    static List<List<Integer>> ll = new ArrayList<>();
    static StringBuffer sb = new StringBuffer();
    static int N;
    static int[] count;

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

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

        count = new int[N+1];
        for(int i = 0; i<=N; i++)
            ll.add(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());

            ll.get(A).add(B);
            count[B]++;
        }

        //위상 정렬
        topologicalSort();

        System.out.println(sb);
    }

    static void topologicalSort(){
        Queue<Integer> q = new LinkedList<>();

        for(int i = 1; i<=N; i++)
            if(count[i] == 0)
                q.offer(i);

        for(int i = 0; i<N; i++) {
            if (!q.isEmpty()) {
                int num = q.poll();
                sb.append(num).append(" ");

                for (int j = 0; j < ll.get(num).size(); j++) {
                    count[ll.get(num).get(j)]--;

                    if (count[ll.get(num).get(j)] == 0)
                        q.offer(ll.get(num).get(j));
                }
            }
        }
    }
}

이 코드에서는 부모 노드의 개수가 몇 개이냐를 따져서 부모 노드가 전부 큐에 들어갔을 때에만 자식 노드를 큐에
넣었습니다.

이 문제에서는 누구의 키가 큰가를 그래프로 나타낸 뒤에 위상 정렬을 이용하여 이를 정렬했습니다.