반응형
이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.
출처 : 파이썬 알고리즘 인터뷰
코드 출처 : 파이썬 알고리즘 인터뷰 깃허브
39. 코스 스케줄
leetcode 207. Course Schdule 문제입니다.
leetcode.com/problems/course-schedule/
풀이
코스를 그래프로 만들고, 그래프가 순환 그래프인지 판단하는 풀이입니다.
def canFinish(self, numCourses,prerequisites):
graph = collections.defaultdict(list)
# 그래프 구성
for x, y in prerequisites:
graph[x].append(y)
traced = set()
visited = set()
def dfs(i):
# 순환 구조이면 False
if i in traced:
return False
# 이미 방문했던 노드이면
if i in visited:
return True
traced.add(i)
for y in graph[i]:
if not dfs(y):
return False
traced.remove(i)
# 탐색 종료 후 방문 노드 추가
visited.add(i)
return True
# 순환 구조 판별
for x in list(graph):
if not dfs(x):
return False
return True
반응형
'Python > 알고리즘' 카테고리의 다른 글
[알고리즘] SCC 찾기 - 코사라주 알고리즘(kosaraju's algorithm) (0) | 2021.04.18 |
---|---|
[알고리즘] 위상정렬 (0) | 2021.04.17 |
[파이썬 알고리즘 인터뷰] 35. 조합 (0) | 2021.03.16 |
[파이썬 알고리즘 인터뷰] 38. 일정 재구성 (0) | 2021.03.13 |
[파이썬 알고리즘 인터뷰] 37. 부분 집합 (0) | 2021.03.13 |