boj 2252 줄 세우기

www.acmicpc.net/problem/2252

2252번: 줄 세우기

자신보다 뒤에 서야하는 학생의 번호를 list에 넣습니다.

그리고 뒤에 서야하는 학생의 번호는 conn 배열을 이용하여 자신보다 앞에 서야하는 학생이 몇명인지 유지합니다.

 

그 다음 conn[i]이 0인 학생들의 번호만 큐에 추가한 후에 bfs를 돌립니다.

 

먼저 번호 x보다 뒤에 서야하는 번호를 하나씩 확인하여 conn[y]--를 해줍니다.

conn[y]=0이 되면 자신보다 앞에 있어야할 번호를 모두 탐색을 했으므로 y를 큐에 추가합니다.

이런 방식으로 ans에 번호를 차례대로 쌓는 방식입니다.

 

이 문제는 줄을 못 세우는 경우가 없기 때문에 ans의 크기가 N보다 작은지 확인하는 예외처리를 하지 않았습니다.

만약 문제에서 이런 경우는 요구하면 무조건 해줘야하는 예외케이스 입니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list[] = new ArrayList[32001];
    static ArrayList<Integer> ans = new ArrayList<>();
    static int conn[] = new int[32001];
    static int N, M;
 
    static void print() {
        for (int i = 0; i < ans.size(); i++) {
            sb.append(ans.get(i) + " ");
        }
        System.out.println(sb.toString());
    }
 
    static void func() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (conn[i] == 0) {
                q.add(i);
            }
        }
 
        while (!q.isEmpty()) {
            int x = q.poll();
 
            ans.add(x);
            for (int i = 0; i < list[x].size(); i++) {
                int y = list[x].get(i);
 
                conn[y]--;
 
                if (conn[y] == 0)
                    q.add(y);
            }
        }
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N; i++)
            list[i] = new ArrayList<>();
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            conn[v]++;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}