교육과정 (위상정렬, 그래프)

교육 과정

• 현수는 n개의 교육 과정을 수료해야 합니다.
• 교육과목에는 선수과목이 있습니다. 만약 ["art math"]라는 정보는 art과목을 수강하기 위해서
  는 math과목을 먼저 수강해야 합니다.
• 매개변수 subjects에 n개의 과목목록이 주어지고 course에 각 과목의 선수과목 정보가 주어지
  면 현수가 n개의 과목을 모두 이수할 수 있는 순서를 배열에 담아 반환하는 프로그램을 작성
  하세요. 답이 여러개면 그 중 아무거나 반환하면 됩니다.
• 현수가 모든 과정을 이수할 수 있는 입력만 주어진다고 가정합니다.

해법

위상정렬

• 위상정렬은 비순환 방향그래프에서 정점을 선형으로 정렬하는 것임, 주로 선후관계가 있는 일련의 작업의 순서를 결정할 때 사용한다.

• indegree가 문제 해법의 key이다. (진입 차수 계산)
• 우선 모든 과목을 string에서 subject배열의 인덱스에 1:1매칭하여 그래프화 하는 것이 좋다
• indegree에는 각 노드의 진입차수를 기록한다.
  • 위 그림을 예시로 들면 art과목의 진입차수는 2이다, math, music이 진입하고 있기 때문

   			Map<String, Integer> map = new HashMap<>();
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < subjects.length; i++) {
            map.put(subjects[i], i);
            list.add(new ArrayList<>());
        }
        int[] indegree = new int[subjects.length];
        for (int i = 0; i < course.length; i++) {
            String[] split = course[i].split(" ");
            int s1 = map.get(split[0]);
            int s2 = map.get(split[1]);
            list.get(s2).add(s1);
            indegree[s1]++;
        }

• 진입차수가 0인것부터 queue에 등록하고 그래프를 순회하면서 문제를 해결한다.
• queue에서 빠진 그래프 노드의 다음 노드들의 indegree값을 하나씩 줄이면서 0이되면 queue에 다시 넣는다.

				Queue<Integer> queue = new LinkedList<>();
			  List<Integer> order = new ArrayList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0)
                queue.add(i);
        }

        while (!queue.isEmpty()){
            Integer now = queue.poll();
            order.add(now);
            List<Integer> nextSub = list.get(now);
            for(Integer sub : nextSub){
                indegree[sub]--;
                if (indegree[sub] == 0)
                    queue.add(sub);
            }
        }

최종 코드

public String[] solution(String[] subjects, String[] course){
        String[] answer = new String[subjects.length];
        Map<String, Integer> map = new HashMap<>();
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < subjects.length; i++) {
            map.put(subjects[i], i);
            list.add(new ArrayList<>());
        }
        int[] indegree = new int[subjects.length];
        for (int i = 0; i < course.length; i++) {
            String[] split = course[i].split(" ");
            int s1 = map.get(split[0]);
            int s2 = map.get(split[1]);
            list.get(s2).add(s1);
            indegree[s1]++;
        }

        List<Integer> order = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0)
                queue.add(i);
        }

        while (!queue.isEmpty()){
            Integer now = queue.poll();
            order.add(now);
            List<Integer> nextSub = list.get(now);
            for(Integer sub : nextSub){
                indegree[sub]--;
                if (indegree[sub] == 0)
                    queue.add(sub);
            }
        }
        for (int i = 0; i < order.size(); i++) {
            answer[i] = subjects[order.get(i)];
        }
        return answer;
    }

참고
자바 코딩테스트 - it 대기업 유제