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

https://www.acmicpc.net/problem/14567

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_14567 {
    static int N, M;
    static int[] dp;
    static ArrayList<Integer>[] prerequisite;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new int[N + 1];
        prerequisite = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            prerequisite[i] = new ArrayList<>();
        }
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            prerequisite[A].add(B);
        }
        Arrays.fill(dp, 1);
        for (int i = 1; i <= N; i++) {
            if(prerequisite[i].isEmpty())
                continue;
            for (int num : prerequisite[i]) {
                dp[num] = Math.max(dp[num], dp[i] + 1);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(dp[i]).append(" ");
        }
        System.out.println(sb);
    }
}

💡 DP

풀이

• 처음에는 BFS로 진행했지만 시간 초과뜸..ㅎㅎ
  • 선수과목이 여러 개인 경우도 존재함!
• DP를 활용하자
  • dp를 진행하기 위해선 앞 과목부터 진행해야 함 (선수과목 번호 < 과목 번호 이므로) -> ArrayList에 1부터 정의
  • DP[과목 번호] = 해당 과목을 수강하기까지 필요한 과목수
  • -> DP[B] = DP[A] + 1
  • 이때, 앞서 말했듯 선수과목이 여러 개인 경우도 존재하므로 무조건 새 값으로 갱신해주면 안됨. 선수과목 중 제일 늦게끝나는 과목 날짜 + 1 해야 함
  • -> DP[B] = Math.max(dp[B], dp[A] + 1) 로 가야 한다