문제들 중, graph 에서 특정 노드를 방문하기 전에 다른 노드를 반드시 방문해야하는 케이스들이 있다. 예를 들어, 수강하고자 하는 강의는 선수강 강의가 있어서 해당 강의를 먼저 들어야 하는등..
이런 경우 DFS 를 통해 문제를 푸는것도 가능하지만, Kahn’s Algorithm 을 통해 문제를 풀 수 있다!
Algorithm
1. inDegree(=incoming path 갯수) 가 0인 node 들을 queue 에 넣는다.
2. queue 에서 node 들을 꺼내면서, 해당 node 를 prerequisite 으로 갖는 node 들의 inDegree를 1씩 감소시킨다.(해당 node를 graph 에서 제거하는 것!)
3. queue 에서 node 들을 꺼내면서 해당 노드 값들을 결과 값에 추가한다!
단, 해당 해결법은 cycle 이 없는 graph 경우에만 가능하다!
Problem
https://leetcode.com/problems/course-schedule-ii/description/
Solution
class Solution {
private Map<Integer, Integer> inDegreeMap = new HashMap<>();
private Map<Integer, List<Integer>> prerequisitesMap = new HashMap<>(); // key 를 prerequisite 으로 갖고 있는 course 들을 value list으로 가진 Map
private int numCourses;
public int[] findOrder(int numCourses, int[][] prerequisites) {
this.numCourses = numCourses;
for (int i=0;i<numCourses;i++) {
inDegreeMap.put(i, 0);
}
// 각 node 의 inDegree 초기화
// 각 node 를 prerequisite 으로 갖는 prerequisitesMap 초기화
for (int i=0;i<prerequisites.length;i++) {
int course = prerequisites[i][0];
int prerequisite = prerequisites[i][1];
int inDegree = inDegreeMap.get(course);
inDegreeMap.put(course, inDegree + 1);
List<Integer> prerequisiteCourses = prerequisitesMap.getOrDefault(prerequisite, new ArrayList<>());
prerequisiteCourses.add(course);
prerequisitesMap.put(prerequisite, prerequisiteCourses);
}
// inDegree 가 0인 노드 queue에 추가
Queue<Integer> queue = new LinkedList<>();
for (int course : inDegreeMap.keySet()) {
int inDegree = inDegreeMap.get(course);
if (inDegree == 0) {
queue.add(course);
}
}
List<Integer> result = new LinkedList<>();
while(!queue.isEmpty()) {
int course = queue.poll();
// inDegree 가 0인 노드 결과에 추가
result.add(course);
// 노드를 prerequisite 으로 갖는 노드들 inDegree 1 씩 감소
List<Integer> nextCourses = prerequisitesMap.getOrDefault(course, new LinkedList<>());
for (int nextCourse : nextCourses) {
int inDegree = inDegreeMap.get(nextCourse);
inDegree -= 1;
inDegreeMap.put(nextCourse, inDegree);
if (inDegree == 0) {
queue.add(nextCourse);
}
}
}
return (result.size() == numCourses)? result.stream()
.mapToInt(Integer::intValue)
.toArray() : new int[0];
}
}
- prerequisitesMap 을 초기화해서, 해당 node 를 prerequisite 으로 갖는 node map 을 저장하는 것이 조금 헷갈렸음!
Will the Guru 
Leave a comment