[알고리즘] 2252번

오늘 풀어볼 문제는 백준 2252번 문제이다.

📌 도전 📌
이 문제는 위상 정렬을 활용해서 풀었다. 연결된 노드가 있을 경우 연결을 당하는 쪽에서 카운트 +1을 하였다. 그리고 노드 정리가 끝난 후 카운트가 0인 값들은 큐에 바로 넣고 큐가 빌 때까지 반복문을 돌리며 같은 행위를 반복하였다.

public class Main {
    static int n;
    static int m;
    static ArrayList<ArrayList<Integer>> arr;
    static int[] ans;
    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());
        m = Integer.parseInt(st.nextToken());

        arr = new ArrayList<>();
        for(int i=0; i <= n; i++) {
            arr.add(new ArrayList<>());
        }
        ans = new int[n+1];

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr.get(s).add(e);
            ans[e]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i=1; i<=n; i++) {
            if(ans[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.println(now + " ");
            for(int next : arr.get(now)) {
                ans[next]--;
                if(ans[next] == 0) {
                    queue.offer(next);
                }
            }
        }
    }
}

[문제 출처] : https://www.acmicpc.net/problem/2252