[14567] 선수과목

✔ 선수과목

[백준 14567]

코드 구현하기

/*
 * 문제 분석하기
 * : 위상 정렬 알고리즘을 이용해 각 과목의 수강 학기를 구하도록 함
 */

/* 
 * 손으로 풀어보기
 * 1. 위상 정렬을 하며 진입 차수가 0인 노드는 1학기 수강
 * 2. 이후 노드의 다음 연결된 노드일 경우 선수 과목의 수강 학기 + 1을 해주도록 함
 */

/*
 * 14567) 선수과목
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int N, M;
    static ArrayList<Integer>[] arr; // arr(선수과목들에 따른 다음 과목 정보)
    static int[] indegree; // indegree(진입차수 배열)
    static int[] semesters; // semesters(수강해야 하는 과목들의 수강학기)

    /*
     * Subject(과목 정보를 담은 클래스)
     */
    static class Subject {
        int id;
        int semester;

        public Subject(int id, int semester) {
            this.id = id;
            this.semester = semester;
        }
    }

    /*
     * 과목의 이수 학기 찾기 준비하기
     */
    static void init(StringTokenizer st) throws IOException {
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new ArrayList[N + 1]; // 각 과목에 연결된 과목 정보를 담기 위한 연결 리스트 초기화
        for (int i = 1; i <= N; i++) {
            arr[i] = new ArrayList<Integer>();
        }

        indegree = new int[N + 1]; // 모든 선수 과목 정보 저장하기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            arr[A].add(B);
            indegree[B]++;
        }

        semesters = new int[N + 1];
    }

    /*
     * 각 과목의 이수 학기 찾기
     */
    static void find() {
        Queue<Subject> queue = new LinkedList<Subject>();
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) { // 진입차수가 0인 과목을 큐에 삽입
                queue.add(new Subject(i, 1));
                semesters[i] = 1;
            }
        }

        while (!queue.isEmpty()) {
            Subject now = queue.poll();
            for (int next : arr[now.id]) { // 해당 선수과목과 연결된 다음 과목을 살펴보기
                indegree[next]--;
                if (indegree[next] == 0) { // 새롭게 진입차수가 0이 되는 과목을 큐에 삽입
                    queue.add(new Subject(next, now.semester + 1));
                    semesters[next] = now.semester + 1;
                }
            }
        }
    }

    /*
     * 각 과목의 이수 학기 출력하기
     */
    static void print() {
        for (int i = 1; i <= N; i++) {
            System.out.print(semesters[i] + " ");
        }
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        init(st);
        find();
        print();
    }
}