[백준] 2252 줄세우기 java 풀이

1. 문제에 대하여 📦

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

(1) 조건 분석 📊

키 순서별로 학생들을 정렬하려 한다.

• 키 순서에는 순환이 존재할 수 없다. (사이클 없는 그래프)
• 키에는 대소가 존재한다. (방향 그래프)
• 키의 대소 관계가 일부만 존재하기 때문에, 답이 여러가지인 경우 아무거나 출력해라

2. 코드가 나오기까지 🛠️

KEY WORD: 위상 정렬

이 문제는 전형적인 위상정렬 문제이다.
만약 위상정렬에 대한 이해가 부족하신 분들은 [알고리즘] 위상정렬, 그림으로 쉽게 설명^^을 보고 오시길 바란다.

처음에는 그저 진입 차수 배열 + for, while 반복문으로 문제를 풀었더니 시간이 963ms 정도로 높게 나왔다.

이를 최적화 하려면 인접리스트 + BFS 방식으로 가장 선행되는 작업을 찾는 방법을 활용해야한다. 자세한 방법은 SUDO CODE에서 말하도록 하겠다.

(1) 시간복잡도 분석 ⏳

정점의 개수를 $N$, 간선의 개수를 $M$ 이라고 할 때,
위상 정렬 자체를 BFS 로 구현했음으로 전체 시간복잡도는 $O(N +M)$ 이다.

3. 코드 🌐

(1) SUDO CODE 💬

+ 0. 인접리스트 생성과 동시에 진입 차수 배열 만들기
+ 1. Queue에 진입 차수가 0인 정점 (가장 선행되는 정점)을 넣고 큐 크기가 0이 될 때까지 다음을 반복
-    (1) front에서 정점 번호를 하나 꺼낸다.
-    (2) 해당 정점의 진입차수 값을 1 줄인다. (0은 현 시점 가장 선행되는 작업, -1은 이미 방문한 지점을 뜻함)
-    (3) 해당 정점에서 방문 가능한 정점들의 진입 차수를 1 줄인다.
-    (4) 만약 (3)번 작업 후 진입 차수 = 0이 되는 지점이 있다면 다음 시점에 가장 선행되어야할 작업임으로 큐에 넣는다.
+ 2. 매 큐 삽입할 때마다 정답에 정점 번호를 추가한다.
+    (각 시점의 가장 선행되어야할 작업들을 차례로 정답에 넣어주면 그것이 곧 '정렬된 순서'이다.)

(2) JAVA CODE ☕

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

public class Main{
    static int N, M;
    static ArrayList<Integer> [] lists;
    static int [] inDegree;
    public static void main(String[] args) throws IOException {
        init();
        topologicalSorting();
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        lists= new ArrayList [N+1];
        inDegree = new int [N+1];
        for (int i = 1; i < N+1; i++) {
            lists[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());
            lists[A].add(B);
            inDegree[B]++;
        }
    }
    public static void topologicalSorting(){
        StringBuilder ans = new StringBuilder();
        ArrayDeque<Integer> aq1 = new ArrayDeque<>();
        for (int i = 1; i < N+1; i++) {
            if(inDegree[i] == 0) {
                aq1.add(i);
                ans.append(i).append(" ");
            }
        }
        while (!aq1.isEmpty()){
            int now = aq1.poll();
            for (int i = 0; i < lists[now].size(); i++) {
                int next = lists[now].get(i);
                inDegree[next]--;
                if(inDegree[next] == 0) {
                    aq1.add(next);
                    ans.append(next).append(" ");
                }
            }
        }
        System.out.println(ans);
    }
}

4. 트러블 슈팅 or 배운 점 📝

A. 인접리스트 기껏 만들고 for, while문으로 현 시점 가장 선행되는 작업을 찾은 것

밑의 것이 for,while문으로 푼 풀이인데,

• 모든 정점이 답이 적힐 때까지, $O(N)$
• 매 번 현재 가장 선행되어야할 정점 찾기 $O(N)$
• 해당 정점과 연결된 정점들 진입 차수 줄이기 $O(M)$

1번 과정 내에 2,3번 과정이 있음으로, 최종적으로 $O(N^2 + M)$이 된다.
만약 문제의 제한시간이 2초가 아닌 1초였다면 해당 풀이는 통과하지 못했을 듯 싶다.

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

public class Main{
    static int N, M;
    static ArrayList<Integer> [] lists;
    static int [] inDegree;
    static ArrayList<Integer> ans = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        init();
        topologicalSorting();
        for(int temp : ans){
            System.out.print(temp + " ");
        }
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        lists= new ArrayList [N+1];
        inDegree = new int [N+1];
        for (int i = 1; i < N+1; i++) {
            lists[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());
            lists[A].add(B);
            inDegree[B]++;
        }
    }
    public static void topologicalSorting(){
        while(ans.size() < N){
            int now = 0;
            for (int i = 1; i < N+1; i++) {
                if(inDegree[i] == 0) {
                    inDegree[i]--;
                    now = i;
                    break;
                }
            }
            ans.add(now);
            for (int i = 0; i < lists[now].size(); i++) {
                inDegree[lists[now].get(i)]--;
            }
        }
    }
}