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

www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

 

1. 문제 설명

 

과목들의 선수과목 조건들이 주어질 때 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 구하는 문제.

 

2. 풀이

 

위상 정렬과 다이내믹 프로그래밍으로 풀 수 있는 문제이다.

 

1) 다이내믹 프로그래밍

X번 과목이 이수할 수 있는 최소 학기를 dp [X]라 할 때 dp [X]는 X의 선수과목들의 최소 학기의 최댓값 +1이다.

 

dp [X]=MAX(dp [Y]+1) (Y는 X의 선수과목)

 

점화식과 선수과목 조건 A B가 주어질 때 A <B라는 점을 이용하여 ( 선수과목 조건이 A> B인 경우가 없기에 1번부터 순서대로 점화식을 구할 수 있다.)

 

1번 과목부터 N번 과목까지 최소 학기를 구한다.

 

2) 위상 정렬

 

진입 차수가 0인 것을 queue에 먼저 넣고 queue에서 값(now)을 꺼내 현재 pre (순서 과목 최소 학기)의 값을 저장한 후 (dp [now]=pre), now 과목을 선수과목으로 둔 과목 중에서 진입 차수가 0인 것은 queue에 저장한다.

 

위상 정렬의 경우 진행 중 진입 차수가 0인 정점이 없다면 위상 정렬 알고리즘을 사용할 수 없는데 이 문제의 경우 선수 과목 조건 A B가 주어질 때 A <B라는 조건이 있기에 위상 정렬을 사용할 수 있다.

 

3. 코드

 

1) 다이나믹 프로그래밍

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));

        int subject_num, condition_num;

        StringTokenizer num=new StringTokenizer(br.readLine());

        subject_num = Integer.parseInt(num.nextToken());
        condition_num = Integer.parseInt(num.nextToken());


        int[] dp = new int[subject_num + 1];
        boolean[][] list = new boolean[subject_num + 1][subject_num + 1];


        for(int x=0;x<condition_num;x++){
            StringTokenizer st=new StringTokenizer(br.readLine());

            int one = Integer.parseInt(st.nextToken());
            int two = Integer.parseInt(st.nextToken());

            list[one][two]=true;
        }


        for (int x = 1; x <= subject_num; x++) {

            dp[x]=1;

            for (int y = 1; y < x; y++) {
                if (list[y][x]) {
                    dp[x] = Math.max(dp[x], dp[y] + 1);
                }
            }
        }

        for (int x = 1; x <= subject_num; x++) {
            bw.write(dp[x] + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }



}

2) 위상 정렬

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));

        int subject_num, condition_num;

        StringTokenizer num=new StringTokenizer(br.readLine());

        subject_num = Integer.parseInt(num.nextToken());
        condition_num = Integer.parseInt(num.nextToken());


        int[] dp = new int[subject_num + 1];
        boolean[][] list = new boolean[subject_num + 1][subject_num + 1];
        int[] in = new int[subject_num + 1];
        Queue<Integer> queue = new LinkedList<>();
        int pre=1;


        for(int x=0;x<condition_num;x++){
            StringTokenizer st=new StringTokenizer(br.readLine());

            int one = Integer.parseInt(st.nextToken());
            int two = Integer.parseInt(st.nextToken());

            list[one][two]=true;

            in[two]++;
        }

        for(int x=1;x<=subject_num;x++){
            if(in[x]==0)
                queue.add(x);
        }

        while(!queue.isEmpty()){

            int queue_size=queue.size();

            for(int x=0;x<queue_size;x++){

                int now=queue.poll();

                dp[now]=pre;

                for(int y=now+1;y<=subject_num;y++){

                    if(list[now][y]){
                        in[y]--;
                        if(in[y]==0)
                            queue.add(y);
                    }

                }
            }

            pre++;
        }


        for (int x = 1; x <= subject_num; x++) {
            bw.write(dp[x] + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }


}

1. 위상정렬 2. 다이나믹 프로그래밍