course schedule 2
https://leetcode.com/problems/course-schedule-ii/description/
문제 파악 [필수 작성]
문제이해
과목을 들어야하는 순서의 리스트를 리턴
가능한 경우가 여러개면 가능한 경우수 중 아무거나 리턴
졸업하는게 불가능하면 빈리스트를 리턴
제한 조건 확인
과목수는 최대 2000개
선후관계는 최대 2000x2000 = 4백만개
-> 딱 간선수만큼만 탐색해라 라는 의미같음
-> 과목수x간선수 되는순간 시간초과
선후관계는 무조건 1대1 매칭
아이디어
졸업불가경우는 그래프 중 순환그래프가 발생하는 경우임
전형적인 위상정렬 문제로 보임
선후관계는 일종의 방향edge 라고 볼 수 있음
가중치 없는 방향그래프로 해석할 수 있음
과목번호는 0번 부터 n-1번까지
자기자신을 가리키는 노드는 없음
전형적인 indegree 를 활용해서 풀 수 있는 문제로 보임
indegree가 같은데 선후관계를 가지는 경우가 있는가? ->
있을 수 있음
반례 : [[3,0],[3,1],[4,2],[4,3]]
정답이 될 수 있는 케이스: [0,1,2,3,4][0,2,1,3,4] [1,0,2,3,4][1,2,0,3,4] 등등
따라서 단순히 indegree 로만 하면 안되고,
indegree 가 0인 노드가 가리키는 다음 노드의 indegree 를 감소시켜줘야함.
만약 감소시켜줬는데 0 이되면 이제 그 과목을 들을 수 있는 상태가 된 것임.
indegree 가 0 인 들을 수 있는 모든 걸 다 들었는데
더 들을 수 있는 0 인게 없고 indegree 가 1 이상인 것들만 있으면
어딘가 사이클이 존재하는 경우이기 때문에 졸업이 불가능한 경우임
시간복잡도
간선의 갯수만큼 while문이 돌기때문에
O(E) = O(400만)
자료구조
접근 방법 [필수 작성]
코드 구현 [필수 작성]
1차 시도 (30분 소요)
한방에 통과!
from collections import defaultdict
from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
n = numCourses
result = []
available = deque([])
edges = defaultdict(list)
indegrees = [0 for _ in range(n)]
for last,first in prerequisites:
edges[first].append(last)
indegrees[last] += 1
for i, indegree in enumerate(indegrees):
if indegree == 0:
available.append(i)
while available:
complete_num = available.popleft()
result.append(complete_num)
for next_num in edges[complete_num]:
indegrees[next_num] -= 1
if indegrees[next_num] == 0:
available.append(next_num)
for indegree in indegrees:
if indegree != 0:
return []
return result
배우게 된 점 [필수 작성]
indegree 배열 초기화해줄때, 도착하는 노드의 indegree 를 늘려줘야하는데 자꾸 거꾸로 출발하는 노드를 늘린다. 거꾸로 적용해줘야하는거 실수하지마!
질문 [ 필수 X ]
Q1
제한 조건 확인, 시간복잡도 계산이 맞는지 확인 한번 부탁드립니다. 특히 제한조건의 의미해석을 제가 문제 의도대로 올바르게 한 게 맞는지 궁금합니다.
답변
제한 조건은 적절하게 이해하신 것이 맞습니다. 시간 복잡도 계산에서 한가지 정정할 것이 있다면 칸 알고리즘은 모든 정점과 간선을 한 번씩 확인하므로 일반적으로 O(V+E)의 시간 복잡도를 갖는다고 표현합니다. 그렇기에 최대 소요 시간을 계산할 땐 400만2천이 조금 더 정확한 표현이라 할 수 있습니다.
