[Grind75-LeetCode] Course Schedule - Medium
접근
- 위상 정렬 (Topological Sort)
- DFS
풀이
2차원 배열로 주어지는 강의를 모두 수강할 수 있는지 구하는 문제이다. 강의 정보는 2차원 배열로 주어지며 [a, b] 형태이다. a라는 강의를 수강하기 위해 b라는 선수 과목을 수강하여야 한다. 언뜻 봤을 때 간단해 보이는 문제로 Set에 강의를 넣어두고 선수 과목이 Set에 들어있는지 확인하고 수강하는 방식으로 진행하면 되지 않을까?라는 접근으로 간단하게 코드를 작성해 봤다. 그럴 경우 예제 2번과 같이 [ [0, 1], [1, 0] ] 0번 강의를 수강하기 위해 1번 강의를 수강해야 하고 1번 강의 수강을 위해 0번 강의를 수강해야 하는 말도 안 되는 경우를 걸러내지 못했다. 그리고 [a, b], [a, c]처럼 a를 수강하기 위해 b, c 모두를 수강해야 하는 경우도 존재한다면 내가 생각한 것과 다른 문제가 되었다.
그렇다 이 문제는 강의가 서로 의존을 가지고 연결된 방향 있는 그래프의 형태이다. 즉 모든 강의가 수강 가능한지 구하는 것은 방향 있는 그래프를 탐색했을 때 모든 정점을 방문할 수 있는지 구하는 문제이고 그래프 내 사이클이 존재하는지 구하는 것과 동일하다. 보통 그래프 탐색을 주로 BFS, DFS를 사용해서 진행했는데 이번 문제는 위상 정렬을 사용하여 풀었고 사이트에 올려져 있던 DFS로 구현된 코드를 하나 가져왔다.
위상 정렬
위상 정렬은 방향 그래프에서 노드를 선형으로 정렬하는 방법이다. 이때 정렬된 결과는 각 노드의 선행 노드가 그 노드보다 앞에 오는 순서를 만족해야 한다. 위상 정렬 또한 DFS로 구현될 수 있지만 이번 코드는 Kahn's 알고리즘으로 구현되었다. Kahn's 알고리즘은 진입 차수를 이용한 위상 정렬 방법이다. 진입 차수란 해당 노드에 도달하기 위해 거쳐야 하는 노드의 개수를 말하는 것으로 선행 노드가 존재하지 않는다면 진입 차수는 0이 된다. 다음은 Kahn's 알고리즘을 통한 동작 방식을 간략하게 나타낸 것이다.
- 각 노드의 진입 차수를 세어 저장하고 선형 그래프를 구성
- 진입 차수가 0인 노드를 큐에 넣고 큐에서 노드를 꺼내 처리하는 방식으로 진행
- 처리 과정에서 노드의 진입 차수를 감소시키고 0이 되는 노드를 큐에 추가
- 최종적으로 처리한 노드의 개수를 세어 모든 정점을 탐색했는지 확인
1단계인 노드의 진입 차수를 세고 그래프를 만드는 과정을 먼저 진행한다.
public boolean canFinish(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 a = prerequisite[0];
int b = prerequisite[1];
graph.get(b).add(a);
inDegree[a]++;
}차수를 세고 그래프를 구성하는 단계의 코드이다. inDegree 배열은 각 노드의 차수를 저장할 배열로 해당 노드로 들어오는 간선의 수를 저장한다. 강의의 개수만큼 정점을 생성해 주고 강의 정보를 통해 각각 연결을 만들어준다. 선행 노드가 존재하는 a의 경우 차수를 올려주게 된다.
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}다음은 진입 차수가 0인 정점들을 큐에 넣는 부분이다. 선행 노드가 존재하지 않는 차수가 0인 노드부터 시작해 연결된 노드들을 타고 올라간다.
int count = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int nextCourse : graph.get(course)) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] == 0) {
queue.offer(nextCourse);
}
}
}
return count == numCourses;
}노드를 처리하고 확인하는 마지막 과정이다. 큐에서 노드를 꺼내 방문했다는 뜻으로 count를 증가시킨다. 그리고 연결된 노드들의 차수를 줄이고 차수가 0이 된 노드가 있다면 선행 강의가 모두 수강되었다는 의미이므로 처리를 위해 큐에 추가한다. 가능한 모든 처리가 끝났다면 처리된 노드의 개수와 강의 개수를 비교해 같다면 모든 강의가 수강 가능한 것으로 true를 반환하고 다르다면 그래프 내 사이클이 존재해 수강이 불가능한 강의가 있는 것으로 false를 반환한다.
실행 시간은 6ms로 대부분의 코드가 해당 시간으로 해결된 것을 볼 수 있다.
DFS
Prerna Dobriyal라는 사람이 해결한 코드로 사이클 존재 여부를 탐지하는 코드이다. 재귀 호출을 통한 DFS로 구현되었다. 코드는 살짝 변경하여 수정된 부분이 존재하고 뒤에서 서술하겠다.
public boolean canFinish(int n, int[][] pre) {
boolean[] visited = new boolean[n];
boolean[] helper = new boolean[n];
List<List<Integer>> al = new ArrayList<>();
for (int i = 0; i < n; i++) {
al.add(new ArrayList<>());
}
for (int[] t : pre) {
al.get(t[1]).add(t[0]);
}위에서부터 방문 체크를 위한 배열, 현재 방문 중인 노드를 추적할 배열, 인접 리스트를 생성하고 그래프를 만들어주는 과정은 동일하다.
for (int i = 0; i < n; i++) {
if (!visited[i]) {
boolean ans = dfs_cyclicDetection(al, i, visited, helper);
if (ans)
return false;
}
}
return true;DFS를 통해 사이클을 탐지하는 코드이다. 방문하지 않은 노드인 경우 메서드를 실행하고 사이클이 존재한다면 false를 반환한다.
public static boolean dfs_cyclicDetection(List<List<Integer>> al, int i, boolean visited[], boolean helper[]) {
visited[i] = true;
helper[i] = true;
List<Integer> neighbour = al.get(i);
for (int k = 0; k < neighbour.size(); k++) {
int curr = neighbour.get(k);
if (helper[curr]) return true;
if (!visited[curr]) {
boolean ans = dfs_cyclicDetection(al, curr, visited, helper);
if (ans) return true;
}
}
helper[i] = false;
return false;
}사이클을 탐지하는 코드이다. 각 방문 체크와 helper를 true로 변경한다. helper 배열은 사이클 탐지를 위해 존재한다. 현재 dfs를 통해 탐색되고 있는 노드에 대한 방문 체크로 true 상태인 helper를 다시 방문하는지에 대해 사이클을 추적한다. 만약 사이클이 존재하지 않는다면 false 상태인 helper만 방문하고 종료될 것이고 사이클이 존재한다면 true 상태인 helper를 다시 방문하게 될 것이다. 그렇게 인접 리스트에 들어있는 정점들을 탐색하며 체크한다.
우선 이 코드의 작성자가 올려준 코드를 그대로 실행시키면 3ms의 실행 시간을 가지는 코드였다. 그러나 몇몇 부분을 보기 편하게 리팩토링 하면서 같이 수정한 부분이 있는데 그 수정으로 인해 1ms 느려지게 되었다.
바로 List 수정으로 1ms 성능 저하가 발생했다. 원본 코드의 경우 모든 List가 ArrayList로 바로 선언이 되어있었다. 자바의 다형성 활용을 위해 해당 부분을 익숙하게 List로 변경하였는데 그렇게 큰 차이를 가져올만한 수정은 아니나 1ms 단위로 차이가 나는 현재 문제에선 큰 변화라고 볼 수 있었다.
우선 List와 ArrayList의 차이에 대해 알고 넘어가야 한다. List는 자바 컬렉션 프레임워크의 "인터페이스" 이고 ArrayList는 해당 List 인터페이스로 구현된 "구현체"이다. 그렇기 때문에 ArrayList로 직접 선언한 경우 바로 구현체에 있는 메서드가 직접적으로 실행된다. 그러나 List로 선언한 경우 인터페이스의 메서드가 실행되어 간접 호출로 인한 오버헤드가 발생한다. 그리고 ArrayList의 경우 배열 기반 구조를 사용하므로 특정 메서드에 대한 성능 최적화가 일어날 수 있지만 List의 경우 여러 구현체를 허용하다 보니 성능 최적화에 대한 구체적인 정보가 부족하여 일어나지 않을 수 있다. 또한 연속적인 메모리 블록에 데이터를 저장하는 ArrayList의 경우 캐시 히트가 잘 일어나지만 List의 경우 다형성을 위해 여러 구현체를 제공하다 보니 메모리 접근 패턴이 최적화 되지 않을 수 있다. 이러한 경우들로 추가적인 성능 차이가 발생하는 것이다.
시간 복잡도
성능 얘기가 나와서 추가한 부분인데 위상 정렬에 사용했던 코드와 아래의 DFS를 사용해 사이클을 탐지하는 코드 둘 다 시간 복잡도는 O(V + E)로 동일하다.
Kahn's 알고리즘 (위상 정렬)
- 그래프 초기화: O(V)
- 진입 차수 계산: O(E)
- 큐 초기화: O(V)
- 각 연결된 강의 탐색: O(V+E)
- 결과: O(V+E)
사이클 탐색 (DFS)
- 그래프 초기화: O(V)
- DFS 탐색: 호출 + 간선 확인 = O(V+E)
- 결과: O(V+E)
동일한 시간 복잡도이나 시간차가 발생하는 이유는 역시나 큐를 사용한 오버헤드 발생과 단순 배열과 메서드 재귀 호출에서 발생하는 차이이다.
전체 코드
Kahn's 알고리즘
class Solution {
public boolean canFinish(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 a = prerequisite[0];
int b = prerequisite[1];
graph.get(b).add(a);
inDegree[a]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int nextCourse : graph.get(course)) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] == 0) {
queue.offer(nextCourse);
}
}
}
return count == numCourses;
}
}
사이클 탐색 (DFS) - ArrayList 사용
class Solution {
public boolean canFinish(int n, int[][] pre) {
boolean[] visited = new boolean[n];
boolean[] helper = new boolean[n];
ArrayList<ArrayList<Integer>> al = new ArrayList<>();
for (int i = 0; i < n; i++) {
al.add(new ArrayList<>());
}
for (int[] t : pre) {
al.get(t[1]).add(t[0]);
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
boolean ans = dfs_cyclicDetection(al, i, visited, helper);
if (ans)
return false;
}
}
return true;
}
public static boolean dfs_cyclicDetection(ArrayList<ArrayList<Integer>> al, int i, boolean visited[], boolean helper[]) {
visited[i] = true;
helper[i] = true;
ArrayList<Integer> neighbour = al.get(i);
for (int k = 0; k < neighbour.size(); k++) {
int curr = neighbour.get(k);
if (helper[curr]) return true;
if (!visited[curr]) {
boolean ans = dfs_cyclicDetection(al, curr, visited, helper);
if (ans) return true;
}
}
helper[i] = false;
return false;
}
}'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글
| [Grind75-LeetCode] Coin Change JAVA (0) | 2024.10.27 |
|---|---|
| [Grind75-LeetCode] Implement Trie (Prefix Tree) JAVA (0) | 2024.10.26 |
| [Grind75-LeetCode] Evaluate Reverse Polish Notation JAVA (1) | 2024.10.24 |
| [Grind75-LeetCode] Clone Graph JAVA (0) | 2024.10.23 |
| [Grind75-LeetCode] Binary Tree Level Order Traversal JAVA (1) | 2024.10.22 |