[Python] 1462. Course Schedule IV

난이도 : medium

 

총 길이가 numCourses인 코스에서 prerequisites라는 path 대로 갈 수 있을 때, queries의 요소들이 각각 이동할 수 있는지 True와 False을 return하는 문제.

 

from collections import defaultdict
class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        
        graph = defaultdict(list)
        for pre, post in prerequisites:
            graph[pre].append(post)

        a = []

        def dfs(start):
            stack = [(start, start)]  # 시작 node, 현재 node
            visited = set()           # 방문한 node 추적용
        
            while stack:
                path_start, current = stack.pop()   # 현재 탐색할 node 가져오기
                if current != path_start:
                    a.append([path_start, current]) # 현재 node와 시작 node가 다르면, 리스트에 추가
                
                visited.add(current)                # 중복 탐색 방지
            
                for neighbor in graph[current]:
                    if neighbor not in visited:
                        stack.append((path_start, neighbor))  # 방문하지 않은 node만 stack에 추가

        for node in list(graph.keys()):
            dfs(node)

        return [x in a for x in queries]

1. graph에 prerequisites의 요소를 하나씩 저장
2. DFS 함수를 정의, stack에는 탐색할 node가 저장되고, visited로 이미 방문한 node를 추적하여 무한 loop 방지
3. 현재 탐색할 node를 stack에서 가져와서, 현재 node(current)와 시작 node(path_start)가 다르면 리스트 a에 추가
4. graph 중 아직 방문하지 않은 node를 stack에 추가
5. DFS 함수 수행
6. 리스트 a 내에 있는 path가 queries에 있는지에 대한 리스트를 return

Runtime : 2769ms (5.02%)

Memory : 20.48MB (47.37%)