home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

วิชาเรียนแบบขนาน (Parallel Courses) ใน Python

สมมติว่ามี N วิชา เเลเบล 1 ถึง N มีอาร์เรย์ความสัมพันธ์ relations[i] = [X, Y] หมายถึงวิชา X ต้องเรียนก่อนวิชา Y

ในหนึ่งภาคเรียน เราสามารถเรียนวิชาได้ไม่จำกัดจำนวน ตราบใดที่เรียนวิชาปัจจัย (prerequisites) ครบแล้ว ต้องหาจำนวนภาคเรียนขั้นต่ำเพื่อเรียนจบทุกวิชา หากเรียนไม่จบคืนค่า -1

เช่น N = 3, relations = [[1,3],[2,3]] ผลลัพธ์คือ 2 เพราะภาคแรกเรียน 1, 2 ภาคที่สองเรียน 3

วิธีแก้ (Topological Sort + BFS Level-by-Level):

  • สร้างกราฟและ indegree array

  • หาโหนดที่ indegree = 0 ใส่คิว (วิชาที่เรียนได้ทันที)

  • ประมวลผลแบบ BFS ระดับต่อระดับ แต่ละระดับ = 1 ภาคเรียน

  • ลด indegree ของเพื่อนบ้าน ถ้าเป็น 0 ใส่คิว

  • นับจำนวนภาคเรียน จนกว่าจะเรียนครบทุกวิชา หรือคิวว่างแต่ยังเหลือวิชา (มี cycle) คืน -1

ตัวอย่างการใช้งาน

class Solution(object):
    def minimumSemesters(self, n, relations):
        courses = n
        visited = [False for _ in range(n+1)]
        queue = []
        graph = [[] for _ in range(n+1)]
        in_degree = [0 for _ in range(n+1)]
        for i in relations:
            graph[i[0]].append(i[1])
            in_degree[i[1]] += 1
        for i in range(1, n+1):
            if not in_degree[i]:
                queue.append(i)
                visited[i] = True
        semester = 1
        courses -= len(queue)
        while queue and courses:
            current_size = len(queue)
            while current_size:
                current_course = queue[0]
                queue.pop(0)
                current_size -= 1
                for i in graph[current_course]:
                    in_degree[i] -= 1
                    if not visited[i] and not in_degree[i]:
                        courses -= 1
                        queue.append(i)
                        visited[i] = True
            semester += 1
        return semester if not courses else -1

ob = Solution()
print(ob.minimumSemesters(3, [[1,3],[2,3]]))

อินพุท

3, [[1,3],[2,3]]

เอาต์พุท

2