https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions
위의 링크에서 Graph 카테고리에 있는 문제를 풀어보았다.

Problem

이 문제를 풀기위해서는 일단 그래프라는 자료 구조가 무엇인지, 그래프를 구현하는 방법에는 무엇이 있는지 알아야한다.

Graph (그래프)

노드(node) 와 그 노드를 연결하는 간선(edge)으로 이루어진 자료구조
cf) 트리 또한 cycle이 허용되지 않는 그래프이다.
node는 다른 말로 vertex라고도 불린다.

아래와 같이 간선의 방향성에 따라 두가지로 나눌 수 있다.

• 방향 그래프 (directed graph): 간선에 방향이 없음. 양방향 가능.
• 무방향 그래프 (undirected graph): 간선에 방향이 있음.

그래프 구현 방법

1. 인접 행렬 (adjacency matrix)
   : 해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다. Edge 개수와는 무관하게 O(V^2) 의 Space Complexity 를 갖는다.

아래 예시는 방향 그래프와 그것을 구현한 인접 행렬을 나타낸다.
길이 존재할 때는 1, 존재하지 않으면 0으로 표현된다.
그래프에서 0->1로 가는 길이 존재하기 때문에 matrix[0,1] = 1이다. 반대로, 1->0은 존재하지 않기 때문에 행렬에서 [1,0] = 0이다.

2. 인접 리스트 (adjacency list):
   vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다. Space Complexity 는 O(E + V)이다.

BFS로 풀기

BFS로 수업들을 하나하나 확인한다. 확인하면서 visited라는 변수에 몇개의 수업을 확인했는지 체크한다. 그래프를 다 돌고 난 후 visited와 주어진 수업들의 개수가 다르다면 cycle이 있는 것이므로 false, 같다면 cycle이 없는 것이므로 true를 리턴한다.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 인접 리스트를 만든다. 
        # course는 0~numCourses-1 사이의 숫자들이므로
        # adj[i]는 course i를 듣고 나서 들을 수 있는 수업들이다.
        adj = [[] for _ in range(numCourses)]
        
        # degree라는 리스트를 만든다.
        # degree[i]는 현재 수업을 듣기전에 들어야하는 수업들, 즉 
        # prerequisites의 개수이다.
        degree = [0] * numCourses
    
        for (curr, pre) in prerequisites:
            adj[pre].append(curr)
            degree[curr] += 1
            
       
      	# queue를 만든다.
        queue = collections.deque([])
        
        # queue에 prerequisite이 필요하지 않은 수업을 저장한다.
        for v in range(numCourses):
            if degree[v] == 0:
                queue.append(v)
              
        # 몇개의 수업을 들었는지 track한다. 
        visited = 0
        
        while queue:
            # 지금 current class 확인
            curr = queue.popleft()
            # mark as visited
            visited += 1
            
            # adj[curr], 즉 curr course를 듣고 난 후 
            # 들을 수 있는 수업들을 확인한다
            for dep in adj[curr]:
                degree[dep] -= 1   
                # degree를 없애는 것은 graph에서 curr 수업을 들었으니 더 확인할 
                # 필요가 없으므로 삭제
                
                # 만약 degree를 없애고 난 후에 degree = 0이면,
                if not degree[dep]:
                # queue에 지금 확인한 dep을 저장하고 또 확인하러 간다
                    queue.append(dep)

	# 확인한 수업들의 개수 == 총 수업 개수가 같으면 cycle이 없는 것이다.
        return visited == numCourses