LeetCode/Top Interview 150

Graphs (싸이클탐지): 210. Course Schedule II★★★

hyunkookim 2024. 12. 17. 17:54

210. Course Schedule II

 

Hint 1
 
This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

 

 
Hint 2
 
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
 
Hint 3
 
Topological sort could also be done via BFS.

 

힌트 1

이 문제는 유향 그래프에서 위상 순서를 찾는 것과 같습니다. 사이클이 있는 경우 위상 순서가 존재하지 않으므로 모든 과정을 수강하는 것은 불가능합니다.

힌트 2

DFS를 통한 위상 정렬 - Coursera의 위상 정렬의 기본 개념을 설명하는 훌륭한 비디오 튜토리얼(21분)

힌트 3

위상 정렬은 BFS를 통해서도 수행할 수 있습니다.

 

문제 요약

이 문제는 위상 정렬(Topological Sort) 알고리즘을 사용하여 해결해야 합니다. 위상 정렬은 그래프의 정점들을 "순서대로 정렬"하는 알고리즘으로, 방향성 있는 비순환 그래프(DAG, Directed Acyclic Graph)에서 주로 사용됩니다.

  • numCourses: 수강해야 할 총 과목 수. 과목은 0부터 numCourses - 1까지 번호가 매겨져 있음.
  • prerequisites: 각 쌍 [a, b]는 과목 a를 듣기 위해 먼저 b를 들어야 함을 의미.
  • 목표: 모든 과목을 완료할 수 있는 순서를 반환하고, 불가능하면 빈 배열 []을 반환.

해결 접근법

  1. 그래프 모델링:
    • 각 과목을 노드로 보고, 선수 과목 관계를 유향 간선으로 표현합니다.
    • prerequisites를 기반으로 인접 리스트를 생성합니다.
  2. 진입 차수 계산:
    • 각 노드(과목)에 들어오는 간선의 개수(진입 차수, in-degree)를 계산합니다.
    • 진입 차수가 0인 노드는 선수 과목이 없는 과목이므로 바로 수강할 수 있습니다.
  3. 위상 정렬:
    • BFS 방식으로 진입 차수가 0인 노드를 큐에 넣고 하나씩 꺼내면서 순서를 기록합니다.
    • 노드에 연결된 다음 노드들의 진입 차수를 감소시키고, 진입 차수가 0이 되면 큐에 추가합니다.
  4. 결과 검증:
    • 모든 노드를 방문했는지 확인합니다. 만약 모든 노드를 방문하지 못했다면 순환이 존재하므로 빈 배열을 반환합니다.

 

코드 (BFS 기반 위상 정렬)

from collections import defaultdict, deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 그래프 초기화 (인접 리스트) 및 진입 차수 초기화
        graph = defaultdict(list)
        in_degree = [0] * numCourses
        
        # 그래프 생성 및 진입 차수 계산
        for course, pre in prerequisites:
            graph[pre].append(course)  # pre -> course
            in_degree[course] += 1     # course의 진입 차수 +1
        
        # 진입 차수가 0인 노드(과목)를 큐에 추가
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        order = []  # 수강 순서 저장
        
        # 위상 정렬 수행
        while queue:
            course = queue.popleft()
            order.append(course)  # 순서에 추가
            
            # 해당 노드와 연결된 노드들의 진입 차수 감소
            for next_course in graph[course]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    queue.append(next_course)
        
        # 모든 과목을 완료할 수 있는지 확인
        return order if len(order) == numCourses else []

 

코드 설명

  1. 그래프 생성
    • graph에 선수 과목 관계를 저장합니다.
    • in_degree 배열에 각 노드의 진입 차수를 저장합니다.
  2. 큐 초기화
    • 진입 차수가 0인 노드를 찾아 큐에 넣습니다.
  3. 위상 정렬
    • 큐에서 노드를 꺼내고, 해당 노드와 연결된 노드들의 진입 차수를 줄입니다.
    • 진입 차수가 0이 되면 큐에 추가합니다.
    • 이 과정을 반복하면서 순서를 기록합니다.
  4. 결과 검증
    • order에 기록된 노드의 개수가 numCourses와 같으면 순서를 반환하고, 아니면 빈 배열을 반환합니다.

 

https://youtu.be/Akt3glAwyfY?si=FskxT3P6hLYgwiu4

 

위상 정렬을 DFS를 사용하여 구현한 것입니다.

위상 정렬은 **유향 비순환 그래프(DAG)**에서 정점의 순서를 정렬하는 방법입니다.

주요 개념

  1. 그래프 표현:
    • 과목을 노드로 보고, 선수 과목 관계를 유향 간선으로 나타냅니다.
    • 이를 **인접 리스트(adjacency list)**를 사용해 prereq라는 딕셔너리에 저장합니다.
  2. DFS를 이용한 탐색:
    • 각 노드는 3가지 상태 중 하나입니다:
      • unvisited: 아직 방문하지 않은 노드.
      • visiting: 현재 탐색 중인 노드 (순환을 감지할 수 있음).
      • visited: 이미 탐색이 완료된 노드.
  3. 순환 감지:
    • DFS 도중 이미 visiting 상태인 노드를 다시 방문하면 순환이 존재하므로 False를 반환합니다.
  4. 결과 저장:
    • DFS 탐색이 완료된 노드는 output 리스트에 저장되며, 최종적으로 모든 노드를 탐색하면 과목 순서가 반환됩니다.
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 위상 정렬(Topological Sort) via DFS using hashset
        # 선수 과목 관계를 저장할 인접 리스트 초기화
        prereq = {c: [] for c in range(numCourses)}

        # prerequisites를 기반으로 그래프(인접 리스트) 생성
        for crs, pre in prerequisites:
            prereq[crs].append(pre)

        # 각 노드(과목)의 상태를 나타내기 위한 집합
        output = []  # 위상 정렬 결과 저장
        visit = set()  # 이미 탐색이 완료된 노드
        cycle = set()  # 탐색 중인 노드 (순환 감지용)

        # DFS 함수 정의
        def dfs(crs):
            # 순환 감지: 현재 노드가 탐색 중(cycle)에 다시 방문된 경우
            if crs in cycle:
                return False  # 순환이 있으므로 실패
            
            # 이미 방문 완료된 노드라면 더 탐색할 필요 없음
            if crs in visit:
                return True  # 탐색 성공
            
            # 현재 노드를 탐색 중 상태로 추가
            cycle.add(crs)
            # 현재 노드의 모든 선수 과목에 대해 DFS 탐색
            for pre in prereq[crs]:
                if dfs(pre) == False:  # 순환이 감지되면 실패
                    return False
            
            # 탐색이 끝났으므로 현재 노드를 탐색 중 상태에서 제거
            cycle.remove(crs)
            # 현재 노드를 방문 완료 상태로 표시
            visit.add(crs)
            # 결과 리스트에 현재 노드를 추가 (위상 정렬 순서)
            output.append(crs)
            return True  # 탐색 성공

        # 모든 과목에 대해 DFS 탐색 시작
        for c in range(numCourses):
            if dfs(c) == False:  # 순환이 감지되면 빈 리스트 반환
                return []

        # 결과 리스트를 반환 (과목 순서)
        return output

 

좀더 최적화

 

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 선수 과목 리스트를 저장할 딕셔너리를 초기화합니다.
        # Initialize a dictionary to store prerequisite lists for each course.
        preReq = {i: [] for i in range(numCourses)}

        # prerequisites 리스트를 기반으로 각 과목의 선수 과목을 매핑합니다.
        # Populate the prerequisite dictionary based on the prerequisites list.
        for crs, pre in prerequisites:
            preReq[crs].append(pre)

        # 순환 여부를 감지하기 위한 집합 (DFS 경로 추적용).
        # A set to detect cycles (used to track nodes in the current DFS path).
        cycle = set()

        # 결과를 저장할 리스트 (위상 정렬 순서를 담음).
        # A list to store the final result (topological order).
        res = []

        # DFS 함수를 정의합니다.
        # Define the DFS function.
        def dfs(crs):
            # 현재 노드가 순환 집합에 있다면, 싸이클이 발생한 것입니다.
            # If the current node is in the cycle set, a cycle has been detected.
            if crs in cycle:
                return False  # 싸이클 감지 시 False 반환
                # Return False when a cycle is detected.

            # 현재 노드가 이미 결과 리스트에 있다면, 이미 탐색이 완료된 것입니다.
            # If the current node is already in the result list, it is already processed.
            if crs in res:
                return True  # 이미 탐색된 경우 True 반환
                # Return True as it has been successfully processed.

            # 현재 노드를 순환 집합에 추가하여 방문 표시를 합니다.
            # Add the current node to the cycle set to mark it as visited in the current DFS path.
            cycle.add(crs)

            # 현재 과목의 선수 과목들을 재귀적으로 탐색합니다.
            # Recursively visit all prerequisites of the current course.
            for pre in preReq[crs]:
                if not dfs(pre):  # 선수 과목을 탐색 중 싸이클 발견 시 False 반환
                    # Return False if any prerequisite fails due to a cycle.
                    return False

            # 모든 선수 과목 탐색이 끝났으므로 순환 집합에서 제거합니다.
            # Remove the current node from the cycle set after exploring all prerequisites.
            cycle.remove(crs)

            # 탐색 완료된 노드는 결과에 추가합니다.
            # Add the current node to the result list after it is fully explored.
            res.append(crs)

            # 탐색이 성공적으로 완료되었음을 표시합니다.
            # Return True to indicate successful processing.
            return True

        # 모든 과목에 대해 DFS를 수행합니다.
        # Perform DFS for all courses.
        for c in range(numCourses):
            if not dfs(c):  # 싸이클 발견 시 빈 리스트 반환
                # Return an empty list if a cycle is detected.
                return []

        # 결과 리스트를 반환합니다.
        # Return the result list containing the order of courses.
        return res

'LeetCode > Top Interview 150' 카테고리의 다른 글

137. Single Number II  (0) 2024.12.18
67. Add Binary  (0) 2024.12.17
530. Minimum Absolute Difference in BST  (0) 2024.12.15
103. Binary Tree Zigzag Level Order Traversal  (0) 2024.12.15
102. Binary Tree Level Order Traversal  (0) 2024.12.15

'LeetCode/Top Interview 150'의 다른글

  • 현재글Graphs (싸이클탐지): 210. Course Schedule II★★★

관련글

티스토리툴바