[boj] 백준 gold5 14567 선수 과목 (Java) - dp

[문제]

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

14567번: 선수과목 (Prerequisite)

 

[풀이]

과목 별 진입차수를 계산하여 진입 차수가 0이면 dp[i]에 1을 저장한다. 이는 선수과목이 없으므로 1학기 째에 바로 들을 수 있음을 의미한다.

dp[i] = k는 i번 과목을 이수하기 위해 필요한 최소 학기를 저장한다.

만약 5번 과목의 선수관계가 1 - 3 - 5, 4 - 5 두 가지 존재한다면 5번 과목을 이수하기 위한 최소 학기는 3학기이다.

즉, 1~n번까지 과목을 순회하며 i번 과목을 선수 과목으로 삼는 j번 과목의 최소 이수 학기는 Math.max(dp[i-1]+1, dp[j])로 갱신해줄 수 있다.

 

[코드]

 

package dp;

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

public class boj_14567_선수과목 {
    static int n, m;
    static int[] dp;
    static int[] in;
    static List<Integer>[] list;
    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());
        
        in = new int[n+1];
        dp = new int[n+1]; //dp[i] = k. i번 과목을 이수하기 위한 최소 학기
        list = new ArrayList[n+1];
        for(int i=0; i<=n; i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int f = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            list[f].add(s);
            in[s]++;
        }

        for(int i=1; i<=n; i++){
            if(in[i]==0){
                dp[i] = 1;
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=0; j<list[i].size(); j++){
                int node = list[i].get(j);
                dp[node] = Math.max(dp[node], dp[i]+1);
            }
        }

        for(int i=1; i<=n; i++){
            System.out.print(dp[i] + " ");
        }
    }
    
}