백준 JAVA 14567번 선수과목

문제 링크: https://www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

 

 

원하는 과목을 듣기 위해선 선수 과목을 들어야 하는 문제이다. 즉 조건을 체크하면서 순서를 체크하는 문제이다.

 

순서대로 입력이 주어지므로 반복문을 통해서 첫 번째 강의부터 마지막 강의까지 조건들을 체크해주면 된다. 

 

한 과목마다 조건의 최댓 값을 찾은 후 +1 해주면 해당 과목을 들을 수 있는 학기가 나온다. 

 

과목마다 들을 수 있는 학기를 arr 배열에 담고 list[해당과목].add(조건)을 정리하여 찾으면 간단하게 풀 수 있다. 

 

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

class node{
    int where;

    public node(int where) {
        this.where = where;
    }
}


public class Main {

    static int n;
    static int m;
    static int [] arr;
    static StringBuilder sb = new StringBuilder();
    static List<node>[] list;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String []s = br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);

        list = new ArrayList[n+1]; // 조건을 담을 list 선언

        for(int i=1; i<=n; i++){
            list[i]= new ArrayList<>();
        }
        arr= new int[n+1]; // 각 과목마다의 필요한 학기 수

        for(int i=0; i<m; i++){
            String[] s1 = br.readLine().split(" ");
            int before = Integer.parseInt(s1[0]); // 조건
            int post = Integer.parseInt(s1[1]); // 해당 과목
            list[post].add(new node(before)); 
        }
        arr[1]=1;
        int max=0;
        for(int i=2; i<=n; i++){
            if(list[i].isEmpty()){  // 조건이 비어있다면 1학기에 들을 수 있다. 
                arr[i]=1; 
            }
            else{
                for(node a: list[i]){ // 조건이 있다면 조건의 최대 학기 수 +1이 된다. 
                    if(max<=arr[a.where]){
                        max=arr[a.where]+1;
                    }
                }
                arr[i]=max;
                max=0;
            }
        }

        for(int i=1; i<=n; i++){
            sb.append(arr[i]+" ");
        }
        System.out.println(sb.toString());
    }
}