#058 · BFS/DFS중간DFS / 방향 그래프 / 사이클 감지

작업 완료 가능 여부

문제

N개의 작업이 있고, 일부 작업은 선행 작업이 필요합니다. [a, b]는 "작업 a를 완료해야 작업 b를 시작할 수 있다"는 의미입니다.

모든 작업을 완료할 수 있으면 true, 순환 의존이 있어 불가능하면 false를 반환하세요.

n=4, prerequisites=[[1,2],[2,3],[3,4]]
→ true (1→2→3→4 순으로 가능)
 
n=3, prerequisites=[[1,2],[2,3],[3,1]]
→ false (1→2→3→1 순환)

시간 복잡도 목표: O(N + E)

예시 1: 선형 의존 → 순환 없음 → true

입력: n = 4, prerequisites = [[1,2],[2,3],[3,4]]

출력: true

예시 2: 순환 의존 → false

입력: n = 3, prerequisites = [[1,2],[2,3],[3,1]]

출력: false

예시 3: 의존 없음 → true

입력: n = 4, prerequisites = []

출력: true

예시 4: 3↔4 순환 → false

입력: n = 4, prerequisites = [[1,2],[3,4],[4,3]]

출력: false

예시 5: 다이아몬드 구조 → 순환 없음 → true

입력: n = 5, prerequisites = [[1,2],[1,3],[2,4],[3,4],[4,5]]

출력: true

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.