[백준, Java] 14567번, 선수과목(그래프 탐색, 위상 정렬)

문제 링크

14567번: 선수과목

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 1~N개의 강의가 있으며, 선수 조건(B강의를 들으려면 A강의를 먼저 들어야 한다)이 존재합니다.

2. 한 학기의 들을 수 있는 과목의 제한은 없으며, 모든 과목은 매 학기 항상 개설한다.

3. 1 ~ N개 강의에 대해서 차례대로 최소 몇 학기에 이수할 수 있는지 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 과목에 대해서 최소 이수 학기를 탐색합니다.

 

3. 탐색을 통해 얻은 각 강의에 대한 최소 학기를 결과로 출력합니다.

 

강의 최소 이수일 구하기(위상 정렬, 그래프 탐색)

 

강의를 이수하기 전에 선수 강의를 모두 이수해야 한다.

 

 

즉, 자신의 선수 과목이 더 이상 존재하지 않으면 강의를 이수할 수 있다.

 

= 이수를 진행할 수 있는 것은 선수 과목 개수가 0일 때이다. 

 

1번째 학기에는 선수 강의가 존재하지 않는 강의를 진행하면 된다.

 

사용해야 하는 정보

 

1. 각 강의에 대한 선수 강의 개수

 

2. 강의를 이수하면, 선수 강의 이행으로 영향을 받는 강의

 

[프로세스]

 

1. 선수 강의가 0인 강의를 이수한다.

 

- int[] child 으로 관리한다.

 

2. 이수한 강의와 관련된 강의의 선수 강의 개수를 감소한다.

 

- 이수한 강의와 관련된 강의의 선수 강의 개수 - 1

- 만약, 감소한 강의가 0이 되면 다음 학기에 이수하도록 Queue 저장

 

 

※ 예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

n : 6

 

m : 4

 

1	2
1	3
2	5
4	5

 

2. 각 과목에 대해서 최소 이수 학기를 탐색합니다.

 

강의에 대한 상태는 아래와 같다.

 

[선수 강의 개수 설정]

강의	1	2	3	4	5	6
선수강의 개수	0	1	1	0	2	0

 

 

[1학기의 이수 가능한 강의(선수 강의 개수가 0인 강의)]

 

{ 1, 4, 6 }

 

[위상 정렬 진행]

 

1학기

 

{ 1, 4, 6 }

 

1번 강의 : (1 ▶ 2, 1 ▶ 3) = child[2], child[3]에 대해서 -1

=  child[2], child[3]이 0이 되기 때문에 다음 학기에 이수 가능

 

4번 강의 :(4 ▶ 5) = child[5]

= child[5]는 0이 되지 않기 때문에 다음 학기에 수강 불가능

 

6번 강의 : 선수 강의가 되는 것이 없다.

 

2학기

 

{ 2, 3 }

 

2번 강의 : (2 ▶ 5) = child[5]에 대해서 -1

=  child[5]이 0이 되기 때문에 다음 학기에 이수 가능

 

3번 강의 :선수 강의가 되는 것이 없다.

 

2학기

 

{ 5 }

 

5번 강의 :선수 강의가 되는 것이 없다.

 

 

[모든 강의를 이수하였을 때 결과]

강의	1	2	3	4	5	6
이수 학기	1	2	2	1	2	1

 

 

3. 탐색을 통해 얻은 각 강의에 대한 최소 학기를 결과로 출력합니다.

 

탐색을 통해서 얻은 최소 이수 결과를 출력합니다.

 

1 2 2 1 2 1을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준으로 강의의 정보를 저장한다.
• child 배열과 node 리스트로 강의의 관계 및 선수 강의 정보를 저장한다.
• 위상 정렬을 통해서 선수 강의 개수를 기반으로 각 강의의 최소 이수일을 탐색합니다.
• 탐색으로 얻은 각 강의의 최소 이수일을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

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

public class Main {
  public static void main(String[] args) throws IOException {
    //입력값 처리하는 BufferedReader
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //결과값 출력하는 BufferedWriter
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine()," ");
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    //선수 강의 개수 배열
    int[] child = new int[n+1];
    List<List<Integer>> node = new ArrayList<>();
    for(int i=0;i<=n;i++){
      node.add(new ArrayList<>());
    }
    //선수 강의 정보 처리
    for(int i=0;i<m;i++){
      st = new StringTokenizer(br.readLine()," ");
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      node.get(a).add(b);
      child[b]++;
    }
    int[] answer = new int[n+1];
    //선수 강의이 없는 강의 Queue 저장
    Queue<Integer> q = new ArrayDeque<>();
    for(int i=1;i<=n;i++){
      if(child[i] ==0){
        q.add(i);
      }
    }
    int cur = 1;
    //위상 정렬을 통한, 선수 강의 기준 그래프 탐색 진행
    while(!q.isEmpty()){
      int size = q.size();
      //현재 이수할 수 있는 과목 처리
      for(int j=0;j<size;j++){
        int now = q.poll();
        answer[now] = cur;
        //현재 강의 처리함으로, 선수 강의 관련 작업
        for(int nxt : node.get(now)){
          child[nxt]--;
          if(child[nxt] == 0){
            q.add(nxt);
          }
        }
      }
      cur++;
    }
    // 1 ~ N 강의에 대한 최소 이수일 BufferedWriter 저장
    for(int i=1;i<=n;i++){
      bw.write(String.valueOf(answer[i]));
      bw.write(" ");
    }
    bw.flush();		//결과 출력
    bw.close();
    br.close();
  }
}