[백준 14567] 선수과목 (JAVA)

백준 14567번 문제 - 선수과목

14567번: 선수과목 (Prerequisite)

---

문제 분석

• 몇몇 과목은 듣기 위해 먼저 들어야하는 선수과목이 존재한다.
• 즉 선수과목을 들어야지만 과목 수강이 가능
• 그럼 민욱이가 해당강의를 듣기 위해 몇학기가 필요한지 각 강의마다 출력해라

추가조건 

 

+ 한 학기에 들을 수 있는 과목 수에는 제한이 없다.

+ 모든 과목은 매 학기 항상 개설된다.

---

해결 키 포인트

 

• 계산을 편리하기 하기 위한 조건만 이해한다면 쉽다.
  • " 한 학기에 들을 수 있는 과목 수에는 제한이 없다. 모든 과목은 매 학기 항상 개설된다. "
    : 선수과목이 두개 이상이라면 둘 중 더 많은 학기가 필요한 강의의 +1 학기가 해당 강의를 듣기 위해 필요한 학기 수다.
    ex) C 강의를 듣기 위해 A, B를 수강해야 함 [ A는 1학기 필요, B는 2학기 필요]
          C 강의는 B(2) + 1 학기만 수강하면 됨
• 정렬을 필요로 한다.
  • " A번 과목이 B번 과목의 선수과목이다. A < B인 입력만 주어진다. "
  • 위 조건을 보고 아 그럼 B과목은 A과목 + 1 학기 수강으로 하면 되겠다 라고 생각하기 쉽다.
    이 경우 예제 1번이 해결되지 않는다. →
    2 3이 입력되고 1 2 가 입력되므로 2번을 수강하기 위해 1번을 수강한다는 것을 모르고 3번 과목을 계산하므로 오류 발생
  • 선수과목 종류를 입력받고 정렬한 후, 계산한다.

---

코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 과목 수 N, 선수 조건의 수 M
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] dp = new int [N+1];

        ArrayList<PreSubject> preSubject = new ArrayList<>();

        for(int i=0;i<M;i++) {
            // B를 들으려면 A를 수강해야함
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            preSubject.add(new PreSubject(A,B));
        }

        Collections.sort(preSubject);

        for(PreSubject n : preSubject) {
            dp[n.B] = Math.max(dp[n.A] + 1, dp[n.B]);
        }

        for(int i=1;i<=N;i++) {
            bw.write(dp[i]+1 + " ");
        }
        bw.flush();
        bw.close();
    }

    static class PreSubject implements Comparable<PreSubject> {
        int A;
        int B;
        public PreSubject(int A, int B) {
            this.A = A;
            this.B = B;
        }
        @Override
        public int compareTo(PreSubject n2) {
            if(this.B == n2.B)
                return this.A - n2.A;
            return this.B - n2.B;
        }
    }
}