문제39: 코스 스케줄

문제

0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을때, 모든 코스가 완료 가능한지 판별하라.

입력


2, [[1,0]]
2, [[1,0], [0,1]]

출력


True
False

풀이

순환 구조 판별

유향 그래프로 만들기
루트로 다시 돌아올 수 있는 경로가 존재한다면 false


dic = collections.defaultdict(list)
for p in range(prerequisites):
	dic[p[0]].append(p[1])

discovered = []
stack = [0]
while stack:
	v = stack.pop()
	if v in discovered:
		return False # 이 조건에서 순환확인
	discovered.append(v)
	for w in dic[v]:
		stack.append(w)


return True if len(discovered) == numCourses else False

[0,1] [1,2]

1: [4]

2: [4]

3: [1,2]

새로운 개념

0→ 1 →2 → 1

0→ 1 → 2 →3 → 4

→ 3 → 4