[백준 / #2252] 줄 세우기(Java)

문제 설명

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

2252번: 줄 세우기

 

---

문제풀이

- 단순 비교해서 풀었더니 시간초과가 났다.

- 찾아보니 위상정렬을 사용해서 푸는문제!

위상 정렬은 순서가 정해져 있는 작업들을 수행해야 할 때, 그 순서를 결정해 주는 알고리즘이다.
선후 관계가 정의된 그래프 구조 상에서 선후 관계에 때라 정렬하기 위해 위상 정렬을 이용할 수 있다.
정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다.
위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야한다.
즉, 그래프가 비순환 유향 그래프여야 한다.

위상 정렬의 구현
1. 진입 차수가 0인 노드를 큐에 모두 넣는다.
2. 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 인접한 노드의 간선을 제거한다.
=> 인접한 노드의 진입 차수를 1 감소시킨다.
3. 간선 제거 후 진입 차수가 0이 된 노드는 큐에 넣는다.
4. 큐가 공백 큐 상태가 될 때까지 2-3 작업을 반복한다.

 

 

package daily14;

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

public class Ac_2252 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        @SuppressWarnings("unchecked")
        List<Integer>[] arr = new ArrayList[N + 1];
        int indegree[] = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[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());
            indegree[b]++;
            arr[a].add(b);
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }
        while (!q.isEmpty()) {
            int c = q.poll();
            System.out.print(c + " ");
            for (int i = 0; i < arr[c].size(); i++) {
                int next = arr[c].get(i);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.add(next);
                }
            }

        }
    }
}