[LeetCode] 1462. Course Schedule IV (Python)

2025. 1. 27. 18:03·알고리즘/LeetCode

 

난이도: Medium

문제 설명


 

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.

  • For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.

Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.

 

You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.

 

Return a boolean array answer, where answer[j] is the answer to the jth query.

 

문제 예제


Example 1:

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.

Example 2:

Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.

Example 3:

Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]

 

제한 사항


  • 2 <= numCourses <= 100
  • 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
  • prerequisites[i].length == 2
  • 0 <= ai, bi <= numCourses - 1
  • ai != bi
  • All the pairs [ai, bi] are unique.
  • The prerequisites graph has no cycles.
  • 1 <= queries.length <= 104
  • 0 <= ui, vi <= numCourses - 1
  • ui != vi

 

Solution(솔루션)


class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        graph = [[] for _ in range(numCourses)]
        path = [[] for _ in range(numCourses)]

        for v1, v2 in prerequisites:
            graph[v1].append(v2)
        
        for i in range(numCourses):
            q = deque([i])
            visited = [False] * numCourses
            visited[i] = True

            while q:
                vertex = q.popleft()
                path[i].append(vertex)

                for next_vertex in graph[vertex]:
                    if not visited[next_vertex]:
                        q.append(next_vertex)
                        visited[next_vertex] = True

        answer = []
        for v1, v2 in queries:
            answer.append(v2 in path[v1])
        
        return answer

 

먼저, prerequisites를 기준으로 그래프를 만들어 주었다.

 

그 후 각 vertex 별로 bfs를 통해 갈 수 있는 vertex를 저장해주었다.

 

마지막으로, answer리스트를 만들고 query에 두번째 요소가 저장해두었던 path에 있다고 하면 True를 저장하고 아니면 False를 저장했다.

 

그리고 answer를 return하였다.

 

bfs를 사용하긴 했지만 brute force 느낌으로 푼 것 같다.


문제: 1462. Course Schedule IV 

 

깃허브: github

 

algorithmPractice/LeetCode/1558-course-schedule-iv at main · laewonJeong/algorithmPractice

하루 한 문제 챌린지. Contribute to laewonJeong/algorithmPractice development by creating an account on GitHub.

github.com

 

 

'알고리즘 > LeetCode' 카테고리의 다른 글

[LeetCode] 785. Is Graph Bipartite? (Python)  (0) 2025.01.30
[LeetCode] 2658. Maximum Number of Fish in a Grid (Python)  (0) 2025.01.28
[LeetCode] 2948. Make Lexicographically Smallest Array by Swapping Elements (Python)  (0) 2025.01.25
[LeetCode] 802. Find Eventual Safe States (Python)  (0) 2025.01.24
[LeetCode] 1267. Count Servers that Communicate (Python)  (0) 2025.01.23
'알고리즘/LeetCode' 카테고리의 다른 글
  • [LeetCode] 785. Is Graph Bipartite? (Python)
  • [LeetCode] 2658. Maximum Number of Fish in a Grid (Python)
  • [LeetCode] 2948. Make Lexicographically Smallest Array by Swapping Elements (Python)
  • [LeetCode] 802. Find Eventual Safe States (Python)
Laewon Jeong
Laewon Jeong
  • Laewon Jeong
    래원
    Laewon Jeong
    글쓰기 | 관리
  • GitHub

    • github.com/laewonJeong
  • 전체
    오늘
    어제
    • 분류 전체보기 (172)
      • Docker 및 Kubernetes (11)
        • Docker (5)
        • Kubernetes (6)
      • Data Engineering (18)
        • Hadoop (5)
        • Spark (5)
        • Kafka (5)
        • Airflow (3)
      • CI|CD (3)
      • 알고리즘 (136)
        • 알고리즘 (2)
        • LeetCode (118)
        • 프로그래머스 (11)
        • BOJ (1)
        • 코딩테스트 대비 (4)
      • 서버 (2)
        • 미니 서버 (2)
      • 잡담 (1)
  • 태그

    누적합
    BFS
    Python
    Kubernetes
    쿠버네티스
    String
    아파치 하둡
    분산처리
    문자열
    programmers
    그래프
    티스토리챌린지
    이진탐색
    우선순위큐
    프로그래머스
    Apache Spark
    알고리즘
    백트래킹
    도커
    코딩테스트
    DP
    분산
    docker
    파이썬
    오블완
    dfs
    heapq
    아파치 스파크
    리트코드
    leetcode
  • 인기 글

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Laewon Jeong
[LeetCode] 1462. Course Schedule IV (Python)
상단으로

티스토리툴바