자바(백준) 2252 줄 세우기

오답 노트 & 새로 알게 된 점

위상정렬을 배우고 처음 푼 문제이다.

 

문제를 접할 때는 위상정렬을 공부하여 , 위상정렬로 문제를 풀었다.

내가 만약에 이 문제를 그냥 봤다면 위상정렬을 생각할 수 있을까? 

그러도록 문제를 읽고 이런 경우에 위상정렬을 쓰는구나라고 생각해야겠다.

 

키 순서대로 줄을 세운다. 모든 키를 재서 정렬하면 된다.

그러나 문제에 주어진 것은 전체의 키가 아닌 A가 B의 앞에 서야한다라고 주어졌다.

그러면 B의 앞에 있어야 하는 것들이 전부 줄을 서고 나서야 B가 설 수 있게 된다.

 

이러한 근거로 위상정렬로 풀게 된다!

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M;
    static int deg[];
    static ArrayList<Integer> A[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        input();
        pro();
        System.out.println(sb);
 
    }
 
    static void pro() {
        Queue<Integer> q = new ArrayDeque<>();
 
        for(int i = 1; i <= N; i++) {
            if (deg[i] == 0) q.offer(i);
        }
 
        while (!q.isEmpty()) {
            int m = q.poll();
 
            sb.append(m).append(" ");
 
            for(int n : A[m]){
                deg[n]--;
                if(deg[n] == 0){
                    q.offer(n);
                }
            }
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
 
        deg = new int[N + 1];
        A = new ArrayList[N + 1];
 
        for (int i = 0; i <= N; i++) A[i] = new ArrayList<>();
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int bef = atoi(st.nextToken());
            int aft = atoi(st.nextToken());
 
            deg[aft]++;
            A[bef].add(aft);
        }
    }
}