[백준] 2252 줄 세우기 - 위상정렬

문제 링크 : https://www.acmicpc.net/problem/2252

🍊해결방법

• 그래프에서 관계가 주어졌기에 위상정렬을 이용해보자
• in 배열을 사용하여 자기 자신보다 앞에서야 하는 숫자의 개수를 체크하자
• in 배열에 값이 0이라는 건 나보다 앞에 없으므로 Queue에 넣어서 그 다음을 확인
• Queue에서 나왔다는 것은 줄을 선 것이므로 해당 num과 관련된 in[idx]-- 로 제거하자

😀풀이

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 = new StringTokenizer(br.readLine());

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

        List<Integer>[] list = new ArrayList[N+1];

        for(int i=1; i<=N; i++){
            list[i] = new ArrayList<>();
        }

        // 늦게나와야하는 걸 체크하기 위해 값이 높을수록 해당 숫자 보다 앞에서야하는 숫자가 많음
        int[] in = 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());

            list[a].add(b);
            in[b]++;
        }

        Queue<Integer> q = new LinkedList<>();

        for(int i=1; i<=N; i++){
            if (in[i] == 0)
                q.add(i);
        }

        StringBuilder sb = new StringBuilder();

        while(!q.isEmpty()){

            int num = q.poll();

            sb.append(num+" ");

            for(int i=0; i<list[num].size(); i++){

                int idx = list[num].get(i);
                // 해당 idx의 앞에 서야할 숫자가 자리에 섰으므로 감소시키기
                in[idx]--;

                // 이제 idx 앞에 있는 숫자 줄에 다 섬 이제 idx 차례
                if (in[idx] == 0)
                    q.add(idx);
            }
        }


        System.out.println(sb);

    }

}