백준 - 줄 세우기(2252) - 위상 정렬 - Java

1. 문제

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

2. 풀이

위상정렬 카테고리를 보지 않았으면 전혀 위상정렬처럼 보이지 않는다...
A가 B앞에 서야한다. 이처럼 순서를 정해서 정렬을 한다 라고 생각하면 위상 정렬 을 떠올리면 될 것 같다.

• 순서가 있는 정렬
• 답이 여러가지 가능일 경우

1. 학생들의 차수를 모두 0으로 초기화 해준다.

2. A가 B보다 앞에 있을 경우 A -> B라는 흐름으로 B의 차수(자신으로 들어오는 간선의 개수)를 증가시켜주고, list.get(A).add(B)를 진행해준다.

3. 차수가 0인 것들을 Queue에 담는다.

4. Queue 에서 뺀 값과 연결된 list의 번호를 가져와서 이 번호의 노드들을 차감하고, 차감된 값이 0인지 확인하여 0이라면 Queue에 넣어준다.

5. Queue에서 poll한 순서대로 출력한 것이 답.

3. 전체 코드

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

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());
        
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        int d[] = new int[N+1];
        for(int i = 0; i <= N; i++){
            list.add(new ArrayList<>());
            d[i] = 0;
        }
        
        for(int m = 0; m < M; m++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            d[b]++;
            list.get(a).add(b);
        }
        
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= N; i++){
            if(d[i] == 0)
                q.add(i);
        }
        
        StringBuilder sb = new StringBuilder();
        
        while(!q.isEmpty()){
            int n = q.poll();
            sb.append(n + " ");
            
            for(Integer i : list.get(n)){
                if(--d[i] == 0){
                    q.add(i);
                }
            }
        }
        System.out.println(sb.toString());
    }
}