[LeatCode] Medium 210 Course Schedule II (Java)

문제 링크

https://leetcode.com/problems/course-schedule-ii/description/

문제 풀이

설명

n개의 코스가 있고, 이 코스를 모두 완료하려면 순서를 정해야 합니다. 코스 간에는 선행 조건(prerequisites)이 주어지며, 특정 코스를 듣기 위해 먼저 들어야 하는 코스가 있습니다. 모든 코스를 완료할 수 있는 순서를 반환하세요. 만약 순서를 정할 수 없다면, 빈 배열을 반환합니다.

예제 1

입력

numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

출력

[0, 1, 2, 3] or [0, 2, 1, 3]

예제 2

입력

numCourses = 1, prerequisites = []

출력

[0]

접근 방식

이 문제는 그래프 탐색 문제로 볼 수 있습니다. 주어진 prerequisites 배열을 통해 코스 간의 선후 관계를 그래프로 표현한 뒤, 정렬된 순서를 찾아야 합니다.

순서를 찾는 데에는 아래 두 가지 알고리즘 중 하나를 사용할 수 있습니다:

1. BFS (Kahn's Algorithm)
   위상 정렬 알고리즘 중 하나로, 진입 차수(In-degree)를 이용하여 사이클 없이 모든 노드를 탐색합니다.
   진입 차수가 0인 노드부터 시작해 차수를 감소시키며 순서를 정합니다.

2. DFS (Depth First Search)
   각 노드를 깊이 탐색하며 방문 상태(Visiting/Visited)를 기록해 사이클 여부를 확인하고, 결과 리스트를 역순으로 쌓아 반환합니다.

여기서는 BFS를 사용한 위상 정렬로 문제를 해결했습니다.

구현

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 그래프 초기화
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 및 진입 차수 배열 생성
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int preCourse = prerequisite[1];

            graph.get(preCourse).add(course);
            inDegree[course]++;
        }

        // 진입 차수가 0인 코스 큐에 추가
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 위상 정렬 수행
        int[] answer = new int[numCourses];
        int index = 0;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            answer[index++] = cur;

            for (int next : graph.get(cur)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 모든 코스를 처리했는지 확인
        return index == numCourses ? answer : new int[]{};
    }
}

코드 설명

1. 그래프와 진입 차수 배열 초기화

   • 그래프는 ArrayList를 활용하여 인접 리스트로 표현했습니다.
   • inDegree 배열은 각 노드(코스)에 대한 진입 차수를 저장합니다.

2. 그래프 및 진입 차수 구성

   • 주어진 prerequisites 배열을 기반으로 그래프를 구성하고, 각 노드의 진입 차수를 업데이트합니다.

3. 진입 차수 0인 노드 큐에 추가

   • 진입 차수가 0인 노드를 큐에 삽입합니다. 이는 선행 조건 없이 바로 들을 수 있는 코스를 의미합니다.

4. BFS 탐색

   • 큐에서 노드를 꺼내면서 해당 노드에 연결된 다른 노드들의 진입 차수를 감소시킵니다.
   • 진입 차수가 0이 된 노드는 큐에 추가합니다.
   • 순서대로 노드를 결과 배열에 저장합니다.

5. 결과 반환

   • 결과 배열에 모든 노드가 포함되어 있다면 반환하고, 그렇지 않다면(사이클이 존재할 경우) 빈 배열을 반환합니다.

시간 복잡도

• 그래프 구성: O(V+E)
  (V는 노드 수, E는 간선 수)
• BFS 탐색: O(V+E)
• 전체 시간 복잡도: O(V+E)