[Java] BOJ14567, 백준 - 선수과목 (Prerequisite)

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

14567번: 선수과목 (Prerequisite)

 

풀이는 간단하다.

 

과목들간의 관계를 방향 그래프로 생각, 정보는 인접 리스트에 담아준다.

과목 그래프의 방향은 그림의 반대방향으로 담아줘야지 나의 선수과목에 뭐가 있는지 쉽게 검색이 가능하다.

 

1. 선수과목이 없는 경우: 1학기에 바로 수강이 가능
2. 선수과목이 있는 경우
   인접 리스트를 통해서 해당 과목의 선수과목들이 뭐가 있는지 판단하고, 선수과목 중 가장 큰 것의 학기에 +1

 

*시간복잡도

선수과목 정보를 입력받을 때 조건이

1≤A<B≤N

이기 때문에 최대 경우의 수는 1000까지의 합인 1000*1000/2=500500 가 되지만
어차피 m범위가 500000까지이기때문에 신경쓰지 않아도 됨

 

코드 리뷰로 군더더기를 제거할 수 있어서 적어봤다.

근데 이거 백준에서는 아래 코드길이가 더 많이나온다. 왜지,,

 

1차코드

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		ArrayList<Integer>[] adj = new ArrayList[n + 1];
		for (int i = 0; i < adj.length; i++)
			adj[i] = new ArrayList<>();

		for (int i = 1; i <= m; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();
			adj[v2].add(v1);
		} // end Input

		int[] semester = new int[n + 1];
		StringBuilder sb = new StringBuilder("1 ");

		for (int i = 2; i <= n; i++) {
			if (adj[i].isEmpty()) {
				sb.append("1 ");
				continue;
			}
			int maxSemester = 0;
			for (Integer prerequisite : adj[i])
				maxSemester = Math.max(maxSemester, semester[prerequisite]);

			semester[i] = maxSemester + 1;
			sb.append((semester[i] + 1) + " ");
		}
		System.out.println(sb);
	}
}

 

2차코드(숏숏)

import java.util.*;

public class Main {

    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] semester = new int[n + 1];
        ArrayList<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
            semester[i] = 1;
        }
        for (int i = 1; i <= m; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            adj[v2].add(v1);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (Integer prerequisite : adj[i])
                semester[i] = Math.max(semester[i], semester[prerequisite] + 1);
            sb.append(semester[i] + " ");
        }
        System.out.println(sb);
    }
}