LeetCode: 207번 (Course Schedule) [JAVA]

문제 링크

https://leetcode.com/problems/course-schedule/

Course Schedule - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 그래프 탐색을 위해 인접리스트 배열, 중복 방문 체크 배열 그리고 사이클 탐색을 위한 분기 체크 배열을 초기화
2. 주어진 노드(강의) 간의 연결관계가 주어진 prerequisites를 돌며 인접리스트 배열에 관계 추가
3. 이후 전체 강의를 돌며 dfs 탐색을 실시
4. dfs 탐색의 경우 기존의 dfs 탐색과 동일하나 사이클 탐지를 위해 분기 표시 배열을 추가 활용하여, 일종의 백트래킹 방식처럼 현재 노드와 연결된 다음 노드로 dfs 탐색 전 후로 해당 배열을 true와 false로 초기화. 이후 dfs 탐색을 하다 해당 노드가 중복 방문한 노드인데 해당 노드의 분기 표시도 true라면 사이클이기 때문에 결과에 false를 표시
5. 결과(result) 반환

 문제에서 찾아야 하는 모든 강의 수강 가능 여부의 경우, 결국 강의 간의 연결 관계에 있어 사이클을 탐지하라는 문제이다. 해당 문제 해결의 경우 사이클 탐지를 위해 dfs 탐색을 활용했는데, dfs 탐색 상 하나의 분기 이후 쭉 다음 노드를 탐색해나가며 더 이상 탐색이 불가능할 때까지 탐색을 하는데, 이 때 탐색하는 노드 중에서 앞선 분기에서 이어진 노드를 다시 방문하게 된다면 사이클인 것을 알 수 있기 때문에 해당 방식을 활용했다.

 우선 중복 방문과 사이클 탐지를 위한 boolean 배열, 그리고 노드들 간의 인접 노드 리스트를 저장하기 위한 ArrayList 배열을 만들고 각각 초기화한다. 이후 주어진 강의 간의 관계 prerequisites를 바탕으로 인접 노드 리스트에 정보를 채운 후, 전체 강의에 대해 dfs 탐색을 진행한다.

 dfs 함수의 경우 일반적으로 동일하게 중복 방문 체크 후 해당 방문에 true 표시 후 해당 노드와 연결된 노드들에 대해 다음 dfs 함수를 호출하는데, 여기에 추가적으로 cycle 배열을 활용해 사이클 탐지를 한다. 일종의 백트래킹과 같은 방식으로 다음 dfs 함수 호출 전 앞뒤로 cycle 배열에 true와 false를 각각 표시해줌으로써 다음 dfs 탐색이 해당 노드 탐색의 연장선임을 표시해주고, 앞서 해당 노드의 중복 방문 체크와 함께 만약 해당 노드가 중복 방문이며 동일한 탐색 분기에 속해있다면, 반환할 결과값을 false로 바꿔준다. 이후 dfs 탐색이 끝나고 결과값을 반환해주면 된다.

 

class Solution {
    boolean[] visited, cycle;
    ArrayList<Integer> adj[];
    boolean result = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new boolean[numCourses];
        cycle = new boolean[numCourses];
        adj = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < prerequisites.length; i++) {//연결관계 설정
            int a = prerequisites[i][0], b = prerequisites[i][1];
            adj[b].add(a);
        }

        for (int i = 0; i < numCourses; i++) {//전체 강의 dfs 탐색
            dfs(i);

            if (!result) {//사이클 탐지 시
                break;
            }
        }

        return result;
    }

    void dfs(int numCourse) {//dfs 탐색
        if (visited[numCourse]) {//중복 방문인 경우
            if (cycle[numCourse]) {//하나의 분기에 속한 경우라면 사이클이므로
                result = false;
            }

            return;
        }

        visited[numCourse] = true;//방문 표시
        cycle[numCourse] = true;//분기 표시

        for (int i = 0; i < adj[numCourse].size(); i++) {//다음 노드들 dfs 탐색
            dfs(adj[numCourse].get(i));
        }

        cycle[numCourse] = false;//분기 표시 초기화
    }
}

결과