[백준] 2252. 줄세우기(Java) [위상정렬]

문제

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

2252번: 줄 세우기

 

알고리즘

위상정렬

 

풀이

1. 진입 차수가 0인 정점을 큐에 삽입한다.

2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.

3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다.

4. 큐가 빌 때 까지 2~3번 반복. 

 

코드

package com.company;

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

public class Test_Tepologe_Sort {
    static int N, M;
    static int[] inDegree;
    static List<Integer>[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        //그래프 연결 및 진입차수 setting
        inDegree = new int[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            inDegree[b]++;
            list[a].add(b);
        }

        //출력
        String ans = topologySort();
        bw.write(ans);
        bw.flush();
        bw.close();
    }

    //위상정렬
    public static String topologySort(){
        StringBuilder sb = new StringBuilder();
        Queue<Integer> q = new LinkedList<>();
        //진입 차수가 0인 정점을 큐에 삽입
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0)
                q.add(i);
        }

        /** 큐가 빌 때 까지 반복 (=모든 원소를 방문 할 떄 까지)
         * 만약 모든 원소를 방문하기 전 큐가 빈다면 싸이클임
         */
        while (!q.isEmpty()) {
            int num = q.poll();
            sb.append(num+" ");

            //꺼낸 정점이 가르키고 있는 모든 간선을 제거한다.
            for(int i=0; i<list[num].size(); i++){
                int next =list[num].get(i);
                inDegree[next]--;

                //진입 차수가 0이된 정점을 큐에 삽입한다.
                if(inDegree[next]==0){
                    q.add(next);
                }
            }
        }
        return sb.toString();
    }
}

 

위상정렬 개념

https://m.blog.naver.com/ndb796/221236874984