leetcode.com 207. Course Schedule

 

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

파이썬 소스: https://bit.ly/3PpsKBJ

 이 문제는 위상정렬(topological sort) 알고리즘으로 풀 수 있는 문제입니다.

Topological sort 알고리즘은 크게 2가지 문제를 해결할 수 있습니다.

1. direct acyclic graph를 정렬해서, topological order를 만들 수 있고, 하나의 DAG에 대해서, 여러개의 topological order를 만들 수 있습니다만….

일단 이문제에서는 1번의 경우가 아니므로, 1번에 대한 자세한 설명은 패스하도록 하구요.

2번, 어떤 directed graph (edge에 방향이 있는 그래프를 말함)이 주어졌을 때, 그래프에 cycle이 존재하는지 알 수 있습니다.

이 문제는 2번을 활용해서, 이문제를 풀 수 있습니다.

Example 2번처럼 1 -> 0, 0 -> 1 이렇게 0, 1번 모두 서로 course를 먼저 수강해야 다음 course를 수강할 수 있는 경우는, 0, 1번 두개의 course 모두 수강할 수 없습니다.

그래프에서는 Example 2번과 같은 경우를 싸이클(cycle)이라고 말하구요, 아래처럼 3개 이상의 vertex가 cycle을 관계일 수 도 있습니다.

0 -> 1, 1 -> 2, 2-> 0

이 문제의 prerequisites변수를 그래프로 그려보면, course 가 vertex가 되고, 2개의 vertex의 관계는 directed edge가 됩니다.

Example 1번을 보면, [[1, 0]] 이구요, 1번 course를 수강하기 위해서는, 0번 course를 수강한 뒤에 수강할 수 있습니다.

따라서, edge를 그려보면, 0 번에서 출발해서, 1번으로 도착하는 0 -> 1과 같이 그릴 수 있습니다.

이 문제에서는 prerequisites변수로 edge만을 인자로 주기 때문에, edge 1개에 있는 2개의 vertex를 보고, 매번 vertex를 만들기 되면, 중복된 vertex를 만들 수 있습니다.

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

vertexes = {} for [fr, to] in prerequisites:     if fr not in vertexes.keys():         vertexes[fr] = [[], []]     if to not in vertexes.keys():         vertexes[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에 따라서, 리스트에 추가합니다.

Topological sort에서 graph에 cycle이 있는지 확인하는 방법은 다음과 같습니다.

1. incoming 에지가 없는 vertex 하나를 선택합니다.

2. 해당 vertex를 graph에서 삭제합니다.

3. vertex를 선택할 수 없을 때 까지, 1~2번을 반복합니다.

4. graph에 남아있는 vertex가 있으면, cycle이 있는 graph 이고,
남아 있는 vertex가 없으면, graph에 cycle이 없다는 의미 입니다.

 

0 -> 1, 1 -> 2, 3->2

위와 같은 그래프가 있다고 가정할 때, 0 번을 지우고, 1번을 지우고(3번을 지울 수도 있음), 그리고 마지막 남은 vertex를 삭제하면, graph에 남아 있는 vertex가 없습니다.

하지만, Example 2번처럼, 1 -> 0, 0 -> 1 이라고 한다면, 0, 1번 vertex모두 incoming edge를 가지고 있으므로, 삭제할 수 있는 vertex가 없고, 따라서, graph에 cycle이 있다는 걸 알게 됩니다.

 

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

 

모든 vertex를 방문해서, incoming edge가 0 인 vertex를 찾아서, queue 리스트에 추가합니다.

 

while len(queue) > 0:     fr, vertex = queue.pop(0)     del vertexes[fr]

 

graph에서 incoming edge가 없는 vertex를 삭제 합니다.

 

for to in vertex[OUTGOING]:     vertexes[to][INCOMING].remove(fr)     if len(vertexes[to][INCOMING]) == 0:         queue.append([to, vertexes[to]])

 

fr vertex를 삭제 했으므로, fr vertex에서 출발해서 도착하는 to vertex를 찾아서, to vertex에서 fr로부터 오는 incoming edge를 모두 삭제합니다.

to vertex가 incoming edge가 없는 vertex가 되었는지 확인해보고, queue list 에 추가합니다.

이 방식으로 queue 리스트가 0이 될 때 까지 while 루프로 지금까지의 과정을 반복 실행한 뒤에, vertexes dictionary에 남아 있는 vertex가 있으면 cycle 이 있으므로, True, 없으면 False를 리턴하여 문제를 풀 수 있습니다.

 

from typing import List OUTGOING = 0 INCOMING = 1 class Solution:     def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:         vertexes = {}         for [fr, to] in prerequisites:             if fr not in vertexes.keys():                 vertexes[fr] = [[], []]             if to not in vertexes.keys():                 vertexes[to] = [[], []]             vertexes[fr][OUTGOING].append(to)             vertexes[to][INCOMING].append(fr)         queue = []         for key in vertexes.keys():             if len(vertexes[key][INCOMING]) == 0:                 queue.append([key, vertexes[key]])         while len(queue) > 0:             fr, vertex = queue.pop(0)             del vertexes[fr]             for to in vertex[OUTGOING]:                 vertexes[to][INCOMING].remove(fr)                 if len(vertexes[to][INCOMING]) == 0:                     queue.append([to, vertexes[to]])         return len(vertexes.keys()) == 0

 

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

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