[자바] 백준 14567 - 선수과목 (Prerequisite) (java)

목차

문제 : boj14567

 

 

필요 알고리즘

• 위상 정렬
  
  • 위상 정렬을 응용해서 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  위상 정렬을 응용해서 해결했다. 아래와 같이 해당 정점에서 선수과목이 몇 개 인지 따로 기록해둔다. 이걸 차수라고 하겠다. 선수 과목이 없는 과목부터 몇 학기에 이수했는지(거리) 알기 위해 bfs를 돌린다. 이 때 큐에 넣을 시 차수를 1씩 빼고, 해당 정점의 차수가 0이 되면 큐에 넣는다. 이 때 마지막에 해당 지점에 도착하면서 차수가 0이 된 시점의 거리가 최소 이수 학기가 된다.

 

  위상 정렬에 대해서는 '이 글'을 어느정도 적어두었다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] cnt = new int[n+1];
        List<Integer>[] edges = new List[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            cnt[b]++;
        }

        int[] dist = new int[n+1];
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (cnt[i]!=0) continue;
            dist[i] = 1;
            q.add(i);
        }

        while(!q.isEmpty()) {
            int cur = q.poll();

            for (int next : edges[cur]) {
                dist[next] = Math.max(dist[next], dist[cur]+1);
                if (--cnt[next] == 0)
                    q.add(next);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(dist[i]).append(' ');
        }
        System.out.println(sb);
    }
}