leetcode.com 210. Course Schedule II

문제 링크: https://leetcode.com/problems/course-schedule-ii/description/

파이썬 소스: https://bit.ly/4afYyRD

위상정렬(topological sort) 알고리즘으로 풀 수 있는 문제입니다. 이 문제를 풀어 보시기 전에, 먼저 꼭 풀어봐야 할 문제가 있습니다. 아래 링크 참고하세요. 이 문제와 같은 알고리즘으로 약간 다르게 푸는 문제 입니다.

https://codapul.blogspot.com/2024/04/leetcodecom-207-course-schedule.html

 

 numCourses변수 값으로 수강해야 할 course가 몇 개 인지 알 수 있습니다. 여기서 Example 3번을 보면, 0번 course 가 prerequisites에 들어 있지 않은 것을 확인할 수 있습니다.

즉, 0번 course를 수강하기 위해서, 미리 수가해야 하는 course가 없습니다. 하지만, Output에서는 0번이 들어 있어야 합니다.

answers = [v for v in range(numCourses)]

따라서, 답으로 리턴 할 answers 변수에 수강해야 할 모든 강의의 번호를 넣어줍니다.

vertexes: dict = {}

Vertex를 저장해 둘 dictionary 타입의 변수, vertexes가 필요하구요, 숫자를 키로 사용해서, 만들어진 각 vertex에 접근할 수 있습니다.

for to, fr in prerequisites:     if fr not in vertexes.keys():         vertexes[fr] = [fr, [], []]     if to not in vertexes.keys():         vertexes[to] = [to, [], []]     vertexes[fr][OUTGOING].append(to)     vertexes[to][INCOMING].append(fr)

 

prerequisites 변수에서 for 루프로 edge를 하나씩 받아서, 출발지 vertex 와 도착지 vertex를 만들어 줍니다. 이 때, keys()에 있는지 확인해보고, 없는 경우만 vertex를 만들어서, 중복된 vertex가 만들어지는 것을 방지합니다.

 Vertex가 만들어 졌으면, 두개의 vertex사이에 서로 연결을 해야 합니다. 이 문제에서 edge는 directed edge라고 말씀드렸 구요, 따라서, vertex를 기준으로, 나에게 오는 방향 edge 인 경우 incoming이라고 하구요, 나에게서 나가는 방향의 edge를 outgoing이라고 합니다.

 Incoming/outgoing에 따라서, 리스트에 추가합니다.

 

문제를 풀기 시작할 때, answers변수에 모든 course번호를 모두 넣었습니다. Vertex로 만들어진 강의는 이후 코드에서 문제를 푸는 코드에서, 다시 answers에 추가될 것이므로, answers변수에서 삭제하겠습니다.

for v in vertexes.keys():     answers.remove(v)

 

 이제 어떤 course를 먼저 수강할 수 있을까요? 먼저 들어야 하는 course가 없는 강의는 먼저 수강할 수 있습니다. 따라서, 그래프 관점에서 보면, incoming edge가 없는 vertex가 먼저 수강할 수 있는 course입니다. Incoming edge의 개수가 0개인 vertex를 찾아서, queue에 넣습니다.

queue = [] for key in list(vertexes.keys()):     if len(vertexes[key][INCOMING]) == 0:         queue.append(vertexes[key])

 

이제 queue에서 하나씩 vertex를 꺼내서, answers에 추가합니다. 미리 들어야 하는 course가 없는 course이기 때문에, 먼저 수강할 수 있습니다.

queue = [] for key in list(vertexes.keys()):     if len(vertexes[key][INCOMING]) == 0:         queue.append(vertexes[key]) while queue:     fr, outgoing, _ = queue.pop(0)     del vertexes[fr]     answers.append(fr)     for to in outgoing:         vertexes[to][INCOMING].remove(fr)         if len(vertexes[to][INCOMING]) == 0:             queue.append(vertexes[to])

 

queue에서 꺼낸 vertex의 outgoing edge를 루핑하면서, 연결되어 있는 다른 vertex의 incoming edge를 삭제합니다. A course를 듣고, B course를 들어야 한다면, A course는 이미 수강했기 때문에, B course도 수강이 가능하도록, incoming edge가 0이 되도록 만들어줍니다.

 만약에 B course를 듣기 전에 C course를 먼저 수강해야 하는 아래와 같은 상태 였다고 가정합니다.

A -> B

C -> B

A와 C 모드 incoming edge가 없는 상태 이기 때문에, queue에 A, C 모두 들어가게 되고, A와 C에서 나온 outgoing edge를 사용해서, B의 incoming edge 2개를 모두 삭제할 수 있습니다.

결과적으로 B course도 queue에 추가되어, answers에 추가됩니다. 이때, A와 C는 이미 answers에 추가된 상태에서, B가 추가되는 것입니다. 여기서, A 와 C 의 순서는 A, C or C, A 둘 다 가능합니다. 중요한 것은 B 가 A, C가 추가된 이후에, answers에 추가되는 것입니다.

 

이렇게 모든 vertex를 처리해서, vertexes에 남이 있는 vertex가 있는지 확인합니다.

if len(vertexes.keys()) == 0:     return answers return []

남아 있는 vertex가 없다면, prerequisites에 따라서, 강의를 모두 수강할 수 있으므로, answers 변수를 리턴합니다.

남이 있는 vertex가 있다면, prerequisites에 따라서 강의를 수강할 수 없다는 것이므로, 빈 리스트 []를 리턴합니다.

그래프 관점에서 이 경우는, 그래프안에 싸이클이 존재해서 위상정렬을 사용해서 정렬할 수 없는 그래프입니다.

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul