인프런 교육 과정

문제

나의 풀이

import java.util.*;

public class TrainingCourse {
    public static String[] solution(String[] subjects, String[] course) {
        int n = subjects.length; // 교육 과목의 개수
        HashMap<String, Integer> node = new HashMap<>(); // key : 교육 과목 이름, value : 인덱스 번호
        for(int i = 0; i < n; i++) {
            node.put(subjects[i], i);
        }
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>()); // 인접리스트 생성
        }
        int indegree[] = new int[n]; // 진입차수 세기 위해 배열 생성
        for(String x : course) { // 그래프 만들면서 진입차수 카운팅하기
            int a = node.get(x.split(" ")[0]); // 해시를 이용하여 과목 이름이 아닌 인덱스 번호를 구하기
            int b = node.get(x.split(" ")[1]);
            graph.get(b).add(a); // b -> a 방향 그래프 생성
            indegree[a]++; // a 노드의 진입차수 1 증가
        }

        // 위상 정렬
        ArrayList<Integer> order = new ArrayList<>(); // 수강 과목 순서 저장
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            if(indegree[i] == 0) { // 진입 차수가 0인 과목들
                queue.offer(i); // 큐에 노드 번호로 넣어주기
            }
        }
        while(!queue.isEmpty()) { // 큐가 빌때까지 반복
            int pre = queue.poll(); // 큐에서 하나 꺼내기
            order.add(pre); // 꺼낸 과목은 수강하므로 order에 넣어주기
            for(int x : graph.get(pre)) { // 그 과목에 의해서 만들어진 진입차수 감소시키기 위해 방향 그래프 탐색
                indegree[x]--; // 해당 과목과 연결된 과목의 진입차수 1 감소
                if(indegree[x] == 0) { // 진입차수가 0인 경우(선수과목 없으므로 수강할 수 있음)
                    queue.offer(x); // 큐에 넣어주기 
                }
            }
        }
        
        String answer[] = new String[n];
        for(int i = 0; i < n; i++) {
            answer[i] = subjects[order.get(i)]; // order 인덱스 번호에 해당하는 과목 이름들 answer에 추가해주기
        }
        return answer;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(TrainingCourse.solution(new String[]{"english", "math", "physics", "art", "music"},
                new String[]{"art math", "physics art", "art music", "physics math", "english physics"})));
    }
}

전체적인 순서를 찾을 때 위상 정렬을 사용해야 한다. 위상 정렬은 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것이다. 주로 선후 관계가 있는 일련의 작업을 차례대로 수행하기 위해 순서를 정할 때 사용하는 알고리즘이다. 해시를 사용해서 과목 이름을 key로 하고 value값을 인덱스 번호로 만들어준다. course를 탐색하면서 key값의 value값을 노드로 해서 방향 그래프를 만들어준다. 그러면서 indegree 배열에 진입차수도 값을 업데이트 해준다. 진입차수가 0인 노드들은 선수 과목이 없다는 뜻이므로 큐에 넣어준다. 그런 다음 큐가 빌때까지 위상정렬을 행하는데 큐에서 노드 번호를 뽑고 이에 해당하는 진입 차수들을 1씩 감소시킨뒤에 order 배열에 넣어준다. 감소시켰을 때 진입차수가 0이된 노드번호들은 큐에 넣어주고 이 과정을 반복한다. 큐가 비어서 끝나게 되면 order 배열 순서대로 있는 인덱스 번호에 해당하는 과목 이름들은 answer 배열에 넣어줘서 리턴해주면 된다.

결과