https://leetcode.com/problems/course-schedule/description/
아이디어가 떠오르지 않아서 시간초과로 솔루션 참고함
위상 정렬을 통해 유향 그래프에 사이클이 존재하는지 여부를 체크하는 것이 핵심
진입차수를 기록하는 별도의 배열을 만들어서 관리하며
인접리스트를 사용해 선행과 후행의 연결고리를 관리한다.
진입차수가 0인 항목부터 순회를 시작한다.
현재 정점에서 다음으로 갈 수 있는 간선이 있는 경우 진입차수를 감소시키고 다음 순회 대상으로 만든다.
하지만 사이클이 존재하는지 체크해야 하기 때문에 1 감소한 진입차수가 0인 경우에만 다음 순회 대상으로 한다. 즉, 원래 진입차수가 2개 이상이면 사이클이 있다고 판단하므로 어차피 오답이 된다.
BFS 기준으로 볼 때 큐에서 뺄 때마다 count를 증가시키고 최종적으로 numCourses과 같다면 사이클 없이 흘러 최종 과목까지 수강 가능하다고 볼 수 있다.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int n = numCourses;
List<Integer>[] adj = new ArrayList[n];
int[] indegree = new int[n];
for (int[] p : prerequisites) {
int target = p[0];
int pre = p[1];
if (adj[pre] == null) {
adj[pre] = new ArrayList<>();
}
adj[pre].add(target);
indegree[target]++;
}
Queue<Integer> que = new LinkedList<>();
for (int i=0; i<n; i++) {
if (indegree[i] == 0) {
que.offer(i);
}
}
int cnt = 0;
while (!que.isEmpty()) {
int current = que.poll();
cnt++;
if (adj[current] != null) {
for (int next : adj[current]) {
indegree[next]--;
if (indegree[next] == 0) {
que.offer(next);
}
}
}
}
return cnt == numCourses;
}
}adj는 adjacency로 인접리스트를 의미한다.
index는 해당 정점이며, index안의 값(리스트)은 해당 정점에서 도달 가능한 정점을 의미한다.
indegree는 진입차수를 의미한다.
indegree[i]는 i정점에 대한 진입차수다. indegree[i]가 2라면 i정점에 진입 가능한 정점의 수(차수)가 2라는 뜻이다.
첫 번째 for문에서는 이를 단순히 세팅해주는 것에 불과하므로 어렵지 않다.
그 후 BFS 방식으로 풀어나갈 것이기 때문에 Queue를 사용해 주는데,
처음 대상이 될 것을 구하는 과정이 두 번째 for문이다.
진입차수가 0인 것을 찾아 que에 넣는다.
이후에는 순회하면서 que.poll() 할 때마다 카운트를 증가시킨다(코스를 수행한 수).
인접리스트가 비어있지 않으면 인접 항목들을 모두 순회하며 진입차수를 감소시키고, 감소된 진입 차수가 0이라면(현재 위치에서만 접근 가능) que에 다시 offer한다.
결과적으로 진입차수가 1씩으로 이어져있는 인접리스트를 모두 순회하게 되는데,
각 순회마다 증가시킨 카운트(코스를 수행한 수)가 numCourses와 동일하다면
모든 코스를 수행할 수 있다는 의미가 된다.
