코스 일정 - 토폴로지 정렬 (Course schedule - Topological sort)

문제 설명

코스 일정 ‑ 토폴로지 정렬 (Course schedule ‑ Topological sort)

문제 설명:

0에서 numCourses ‑ 1까지 레이블이 지정된 총 numCourses 과정이 있습니다. ] = [ai, bi]는 코스 ai를 수강하려면 코스 bi를 먼저 수강해야 함을 나타냅니다.

예를 들어, 쌍 [0, 1]은 코스 0을 수강하기 위해 반드시 거쳐야 함을 나타냅니다. 먼저 코스 1을 수강하십시오. 모든 코스를 마칠 수 있으면 true를 반환하십시오. 그렇지 않으면 false를 반환합니다.

구현:

이 문제는 토폴로지 정렬의 개념을 사용합니다. 따라서 이 개념에 따라 Stack 및 DFS를 사용하여 구현하려고 하지만 색인이 범위를 벗어납니다. https://www. geeksforgeeks.org/topological‑sorting/. 아래는 내 코드입니다.

public class Solution {
    Stack<int> stack = new Stack<int>();
    bool[] visited = null;
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        visited = new bool[numCourses];

        for(int i = 0; i < numCourses; i++){
            if(visited[i] == false)
                DFS(i, prerequisites);
        }
        return numCourses == stack.Count;
    }

    private void DFS(int course, int[][] prerequisites){
        visited[course] = true; // index out of bounds exception here

        for(int i = 0; i < prerequisites[course].Length; i++)
            if(!visited[prerequisites[course][i]])
                DFS(prerequisites[course][i], prerequisites);

        stack.Push(course);
    }
}

테스트‑1:

2

[[1,0]]

결과: 범위를 벗어난 색인 예외로 인해 실패

테스트‑2:

2

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

결과: 출력은 true이지만 예상은 false입니다.

다른 구현(BFS, 대기열 사용)이 있지만 구현할 수 있는지 알고 싶었습니다. DFS와 스택을 사용합니다. 작동하는 솔루션이 있지만 코드 구현에 도움이 필요하고 누군가가 나를 올바른 방향으로 안내해 줄 수 있다면 도움이 필요합니다.

[[1,0]]

결과: 범위를 벗어난 색인 예외로 인해 실패

테스트‑2:

2

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

결과: 출력은 true이지만 예상은 false입니다.

다음이 있습니다. 다른 구현(BFS, 대기열 사용)이 있지만 DFS와 스택을 사용하여 구현할 수 있는지 알고 싶었습니다. 작동하는 솔루션이 있지만 코드 구현에 도움이 필요하고 누군가가 나를 올바른 방향으로 안내해 줄 수 있다면 도움이 필요합니다.

[[1,0]]

결과: 범위를 벗어난 색인 예외로 인해 실패

테스트‑2:

2

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

결과: 출력은 true이지만 예상은 false입니다.

다음이 있습니다. 다른 구현(BFS, 대기열 사용)이 있지만 DFS와 스택을 사용하여 구현할 수 있는지 알고 싶었습니다. 작동하는 솔루션이 있지만 코드 구현에 도움이 필요하고 누군가가 나를 올바른 방향으로 안내해 줄 수 있다면 도움이 필요합니다.

참조 솔루션

방법 1:

I think the problem comes from the prerequisites data and how you use it : The prerequisites are array of 2 numbers, the first being the course you want to take, the second one of its prerequisites.

private void DFS(int course, int[][] prerequisites){
    visited[course] = true; // index out of bounds exception here

    for(int i = 0; i < prerequisites[course].Length; i++)
        if(!visited[prerequisites[course][i]])
            DFS(prerequisites[course][i], prerequisites);

    stack.Push(course);
}

In this function, you call prerequisite[course].Length, expecting it to give you all prerequisite of the course, but you'll get a random prerequisite. What you need to do is :

private void DFS(int course, int[][] prerequisites){
    visited[course] = true; // index out of bounds exception here

    for(int i = 0; i < prerequisites.Length; i++) // Check all prerequisites
        if(prerequisites[i][0] == course && !visited(prerequisite[i][1]){ 
        // If this is a prerequisite for target course 
        // and we haven't visited the requisited course
            DFS(prerequisites[i][1], prerequisites); // We visit the prerequisite course
        }
    stack.Push(course);
}

(by Souvik Ghosh、Alois Christen)

참조 문서

1. Course schedule ‑ Topological sort (CC BY‑SA 2.5/3.0/4.0)