[백준] 14567. 선수과목 (위상정렬/Java)

[백준] 14567. 선수과목

 

[백준] 2623. 음악프로그램 → 헷갈리면 이 문제도 풀어보자!

📌 풀이 과정

위상정렬 알고리즘 문제!!

위상 정렬 구현

1. 진입 차수가 0인 정점(시작 정점)를 큐에 모두 넣는다.

2. 큐에서 진입 차수가 0인 정점을 꺼내어 자신과 인접한 정점의 간선을 제거한다.
     → 인접한 정점의 진입 차수를 1 감소시킨다.

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

 

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 메모리 : 128584 KB
 * 시간 : 576 ms
 */
public class Main {

    static int N, M;
    static List<Integer>[] subject;
    static int[] inDegree, answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 과목의 수
        M = Integer.parseInt(st.nextToken()); // 선수 조건의 수

        subject = new ArrayList[N + 1];
        inDegree = new int[N + 1];
        answer = new int[N + 1];

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

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            subject[a].add(b); // a는 b의 선수과목
            inDegree[b]++;
        }

        topology();
        for(int i = 1; i <= N; i++){
            System.out.print(answer[i] + " ");
        }

    }


    private static void topology(){
        Queue<int[]> q = new LinkedList<>();
        for(int i = 1; i <= N; i++) {
            if(inDegree[i] == 0) {
                q.add(new int[]{i, 1});
            }
        }

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int idx = cur[0]; // 과목 번호
            int term = cur[1]; // 학기

            answer[idx] = term;

            for(int i : subject[cur[0]]){
                inDegree[i]--;
                if(inDegree[i] == 0) q.add(new int[]{i, term + 1});
            }
        }
    }
}

 

 

추가적인 조건이 있다면?

만약 이 문제에서 "모든 과목을 수강하지 못하는 경우"가 존재한다면 어떤 조건이 필요할까?

위상 정렬이 끝난 후, 정렬된 과목의 수가 총 과목 수와 같은지 확인하면 된다!

정렬된 과목의 수는 processedCount 변수를 전역으로 선언해 main 메서드에서 확인해도 될듯하다.

    private static void topology(){
        Queue<int[]> q = new LinkedList<>();
        int processedCount = 0; // 큐에서 처리된 과목 수를 세는 변수

        for(int i = 1; i <= N; i++) {
            if(inDegree[i] == 0) {
                q.add(new int[]{i, 1});
            }
        }

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int idx = cur[0]; // 과목 번호
            int term = cur[1]; // 학기

            answer[idx] = term;
            processedCount++; // 과목이 처리될 때마다 증가

            for(int i : subject[cur[0]]){
                inDegree[i]--;
                if(inDegree[i] == 0) q.add(new int[]{i, term + 1});
            }
        }

        // 만약 처리된 과목 수가 전체 과목 수와 다르면, 사이클이 발생한 것이므로 -1 출력
        if(processedCount != N) {
            System.out.println(-1);
        } else {
            for(int i = 1; i <= N; i++){
                System.out.print(answer[i] + " ");
            }
        }
    }