[Leetcode] 207. Course Schedule

문제 요약

• 알고리즘 분류: 백트레킹, DFS, 위상정렬
• 난이도: Medium
• 문제내용:
  • 강의 수 numCourse와 prerequisites 배열을 준다.
  • prerequisites[i]는 [a, b]가 들어 있다. b 수강 하기 위해서는 a수강을 먼저 들어아한다.
  • 수강 들을수 있는지 참/거짓으로 반환 하여라.
• 사이트 주소: https://leetcode.com/problems/course-schedule/

문제풀이

 이번 문제는 깊이우선탐색, 백트레킹, 위상정렬을 활용한 문제이다. 두개에 관련 설명은 아래 글에서 확인하면 된다.

• 깊이우선탐색(DFS): https://jih3508.tistory.com/94
• 백트레킹: https://jih3508.tistory.com/84
• 위상 정렬: https://namu.wiki/w/%EC%9C%84%EC%83%81%20%EC%A0%95%EB%A0%AC

문제 접근방법

 이번 문제는 사이클 여부만 확인 하면 문제이다. 그 이유는 b수강 하기 위해서는 a 수강을 해야 한다. 그런데 수업중 선 수업 안들어도 되는 과목이 몇개가 있을것이다. 그러면 선수업 듣기위해서 역추적 해보면 자기 자신으로 돌아오면 수강 할수 없는 구조가 된다. 모든 과목을 탐색해서 자기 자신으로 돌아오는지 확인 하면 문제를 풀수 있다.

 하지만 모든 과목을 하나씩 시작점으로 다 탐색 한면 N은 강의 수, V는 정점의 수,E는 간선의 수 시간 복잡도는 O(N * (E + V))만큼 걸린다. 하나씩 다 탐색 말고 이전 탐색 한 것은 그냥 True로 넘기는 방식으로 가면 된다. 그 이유는 그 노드에서 시작했을때 이미 자기 자신으로 돌아 올수 없기 때문에 그러므로 다음 노드에서 탐색 안하고 다른 노드를 탐색하면 된다.

그러면 시간 복잡도는 O(E + V)만큼 탐색 하면된다. 구현은 아래와 같이 한다.

1. 방문여부 visited와 이전 탐색 경로저장할 trace 초기화한다.
2. 0번 수업부터 N번 수업까지 DFS 탐색을 한다.  
3. 노드에서 방문 여부가 있으면 참으로 반환한다.
4. 현재 노드가 경로에 있으면 False로 반환 한다.
5. 3번 4번 해당 사항이 없으면 다음 필수 수강을 방문 여부 True로 주고 trace에 현재 과목을 추가한다.
6. 다 탐색하면 True로 반환 하고 trace에 현재 수강 과목을 지운다.
7. 2번 과정에서 하나라도 False나오면 바로 False로 반환 한다. 하나라도 안나오면 True로 반환한다.

 이번 문제는 좀 고민을 해야 하는 문제이지만 조금만 더 생각하면 풀 수 있는 문제라고 생각 한다.

Code

 set을 사용하면  포함여부 시간복잡도는 O(1)된다.

Python

class Solution:
    def canFinish(self, numCourses, prerequisites):
        needCourses = {i : [] for i in range(numCourses)}
        for prerequisite in prerequisites:
            needCourses[prerequisite[1]].append(prerequisite[0])
        trace = set()
        visited = [False] * (numCourses)


        def dfs(num):
            if num in trace:
                return False
            if visited[num]:
                return True

            trace.add(num)
            for course in needCourses[num]:
                if not dfs(course):
                    return False

            trace.remove(num)
            visited[num] = True
            return True

        for course in range(numCourses):
            if not dfs(course):
                return False

        return True

Java

import java.util.*;

class Solution {
    Set<Integer> trace;
	boolean[] visited;
	Map<Integer, List<Integer>> needCourse;

	public boolean canFinish(int numCourses, int[][] prerequisites) {
		trace = new HashSet<>();
		visited = new boolean[numCourses];
		Arrays.fill(visited, false);
		needCourse = new HashMap<>();
		
		for(int[] prerequisite : prerequisites) {
			if (!needCourse.keySet().contains(prerequisite[1])){
				needCourse.put(prerequisite[1], new ArrayList<>());
			}
			needCourse.get(prerequisite[1]).add(prerequisite[0]);
		}
		
		for(int i = 0; i < numCourses; i++) {
			if(!dfs(i)) {
				return false;
			}
		}
		
	    return true;    
	}
	
	public boolean dfs(int num) {
		
		if(trace.contains(num)) {
			return false;
		}
		
		if(visited[num]) {
			return true;
		}
		
		trace.add(num);
		
		if(needCourse.keySet().contains(num)) {
			for(int course : needCourse.get(num)) {
				if (!dfs(course)){
					return false;
				}
			}
		}
		trace.remove(num);
		visited[num] = true;
		
		
		return true;
	}
}