[Java] 백준 14567번 - 선수과목 (위상 정렬)

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

14567번: 선수과목 (Prerequisite)

 

문제

올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.

1. 한 학기에 들을 수 있는 과목 수에는 제한이 없다.
2. 모든 과목은 매 학기 항상 개설된다.

모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.

입력

첫 번째 줄에 과목의 수 N(1≤N≤1000)과 선수 조건의 수 M(0≤M≤500000)이 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다. A번 과목이 B번 과목의 선수과목이다. A<B인 입력만 주어진다. (1≤A<B≤N)

출력

1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지를 한 줄에 공백으로 구분하여 출력한다.

 

 

---

 

 

접근 방법

 

- cntArr[i] : i 과목을 들을 수 있는 최소 학기 수 저장. 처음에 모두 1로 초기화 한다. (1<=i<=N)

 

- list<Pair> : 입력받은 선수 과목의 조건을 저장한다. 모두 입력받은 뒤 Pair 클래스의 first 속성을 기준으로 list를 오름차순 정렬한다. (정렬 하지 않으면 '틀렸습니다' 출력)

 

조건 수(list.size()) 만큼 반복하면서 cntArr[second] = cntArr[first] + 1 로 갱신해나간다. 단, RHS가 LHS 보다 클 때만 갱신해준다. 

=> 이유

   예) 6 4

         1 2

         1 3

         2 5

         4 5

일때, arr[2] = arr[1] + 1 = 2

         arr[3] = arr[1] + 1 = 2

         arr[5] = arr[2] + 1 = 2 + 1 = 3

         arr[5] = arr[4] + 1 = 2 -> 이 때 3에서 2로 갱신되면 안 되기 때문.

 

 

import java.util.*;


class Pair{

	Integer first, second;
	public Pair(Integer f, Integer s) {
		this.first= f;
		this.second = s;
	}
	public Integer getFirst() {
		return this.first;
	}
	public Integer getSecond() {
		return  this.second;
	}
	
};

class Comp implements Comparator<Pair>{				//첫번째 선수과목 기준으로 오름차순 정렬
	@Override
	public int compare(Pair p1, Pair p2) {
		if(p1.getFirst() < p2.getFirst()) return -1;
		else if(p1.getFirst() > p2.getFirst()) return 1;
		else return 0;
		
	}
}

public class 위상정렬_BFS14567_선수과목 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		ArrayList<Pair> list = new ArrayList<Pair>();
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		for(int i = 0; i<M; i++) {
			int first = sc.nextInt();
			int second = sc.nextInt();
			list.add(new Pair(first,second));
		}
		
		list.sort(new Comp());
		
		
		int[] cntArr = new int[N+1];
		for(int i = 1; i<=N; i++) {
			cntArr[i] = 1;			//모든 과목은 최소 1학기 
		}
		
		for(int i = 0; i<list.size(); i++) {
			
			int f = list.get(i).getFirst();
			int s = list.get(i).getSecond();
			
			int edgeCnt = cntArr[f] + 1;
			if(edgeCnt > cntArr[s]) {			//이때만 갱신해줘야함
				cntArr[s] = edgeCnt;
			}
		}
		
		for(int i = 1; i<=N; i++) {
			System.out.print(cntArr[i] + " ");
		}
		
		
	}
}