[C] LeetCode 207. Course Schedule

문제

번역

총 numCourses 개의 과목이 있고, 0번부터 numCourses-1번까지 번호로 라벨링이 되어 있다.

prerequisites 배열의 i번째 원소는 a, b로 되어 있는데, 이는 a과목을 듣기 위해서는 b과목을 먼저 들어야 한다는 것을 의미한다.(선수과목)

만약 모든 과목을 들을 수 있다면 true를, 그게 불가능 하다면 false를 반환해라.

 

접근 방법 및 소스코드

선수과목의 관계를 방향 그래프로 생각해보자.

 

자료구조개론과 알고리즘개론 수업이 있다고 해보자.

알고리즘개론 수업을 듣기 위해서는 자료구조개론 수업을 먼저 들어야 한다.

이 경우에는 자료구조개론 -> 알고리즘개론 으로 간선이 그려질 것이다.

이와 함께 자료구조개론 수업을 듣기 위해서는 알고리즘개론 수업을 먼저 들어야 한다.

이 경우에는 알고리즘개론 -> 자료구조개론 으로 간선이 그려질 것이다.

 

이러한 경우 방향 그래프에 사이클이 생기게 되고, 사이클이 생기면 이 수업을 듣는 것은 불가능하다는 것을 알 수 있다.

 

즉, 우리는 선수과목 관계를 인접 매트릭스를 통해 그래프로 만들고, 그래프 탐색을 통해 사이클이 발생하는지 찾으면 된다.

 

DFS 탐색을 하고, 방문 상태를 저장하는 배열인 visited 가 있다. visited의 경우 3가지로 나뉜다.

0 = 아직 방문을 하지 않은 상태

1 = 방문해서 처리중인 상태

2 = 탐색이 완료된 상태

 

만약 사이클이 있다면 dfs도중 상태가 1인 노드를 만날 것이다.

이를 코드로 구현하면 아래와 같다.

 

int graph[2000][2000];
int visited[2000];
int n;

bool dfs(int vertex) {
    if(visited[vertex] == 1) return false; // find cycle.
    if(visited[vertex] == 2) return true; // already check.
    visited[vertex] = 1; //tmp
    for(int i=0;i<n;i++) {
        if(graph[vertex][i] != 0 && !dfs(i)) return false; 
    }
    visited[vertex] = 2; //check. this is safe.
    return true;
}

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) {
    n = numCourses;
    
    memset(graph, 0, sizeof(graph)); memset(visited, 0, sizeof(visited));

    for(int i=0;i<prerequisitesSize;i++) {
        graph[prerequisites[i][0]][prerequisites[i][1]] = 1;
    }

    for(int i=0;i<n;i++) {
        if(visited[i] == 0 && !dfs(i)) return false;
    }
    return true;
}

 

 

통과는 했지만 그렇게 좋은 소스코드는 아닌 것 같다.