백준 q14567 - 선수과목 (Prerequisite)

14567번: 선수과목 (Prerequisite)

---

의식의 흐름

선수 과목에 대한 Arraylist 배열(subjects)을 만들고 개수를 세면 되지 않나,,
이후에 'A < B인 입력만 주어진다'는 조건을 제대로 안보고 시작 과목을 어떻게 정하지?하고 엄청 헤맸다👻

풀이 과정

1. 과목의 수(N), 선수 조건의 수(M)를 입력 받는다.
2. 어떤 과목의 선수 과목인지 담을 배열(subjects)과 선수과목 수를 담을 배열(dp)를 생성한다.
- subjects : ArrayList[]
- dp : int[]
3. subjects를 채우고 dp는 1로 초기화한다.
4. 선수과목이 i번 과목인 과목들에 대해 dp를 구한다.

for(int i=1;i<=N;i++){
    ArrayList nextSubjects = subjects[i];
    int nextSubjectCnt = nextSubjects.size();

    for(int j=0;j
        int nextSubject = nextSubjects.get(j);
        dp[nextSubject] = Math.max(dp[nextSubject], dp[i]+1);
    }
}

 

5. dp를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static int N,M;
    public static ArrayList<Integer>[] subjects;
    public static int[] dp;

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

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

        subjects = new ArrayList[N+1]; // subjects[i] = 과목i가 어떤 과목들의 선수과목인가
        dp = new int[N+1]; // 선수과목 수
        for(int i=1;i<=N;i++){
            subjects[i] = new ArrayList<Integer>();
            dp[i] = 1;
        }
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int prerequisite = Integer.parseInt(st.nextToken());
            int subject = Integer.parseInt(st.nextToken());

            subjects[prerequisite].add(subject);
        }


        for(int i=1;i<=N;i++){
            ArrayList<Integer> nextSubjects = subjects[i];
            int nextSubjectCnt = nextSubjects.size();

            for(int j=0;j<nextSubjectCnt;j++){
                int nextSubject = nextSubjects.get(j);
                dp[nextSubject] = Math.max(dp[nextSubject], dp[i]+1);
            }
        }

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

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