207. Course Schedule (Java, topology, Leetcode)

토폴로지 문제를 풀던 중 다른 사람의 직관적인 풀이를 발견하여 기록해둔다.

 

 

모든 노드간 연결을 List<List<>> 형태의 그래프로 저장한다.

 

각 노드를 돌면서 DFS를 시행하고 만약 cycle이 내부에서 발견된다면 return false를 한다.

(e.g. 0을 수행하기 위해서 1이 필요하고 1을 수행하기 위해서 0이 필요한 경우가 동시에 발견될 경우)

 

DFS의 상태값을 (미방문, 방문중, 방문끝) 을 나타내는 enum을 통해 관리한다.

 

class Solution {
	//미방문, 방문중, 방문끝 
    enum Status {
        VISITING, VISITED;
    }
    private boolean dfs(List<List<Integer>> graph, Status[] visited, int i) {
        //다시 방문한 노드가 VISITING 상태라면 cycle
        if (visited[i] == Status.VISITING) return true;
        if (visited[i] == Status.VISITED) return false;
        
        visited[i] = Status.VISITING;
        for (var next : graph.get(i)) {
        //cycle이 형성되었다면 return true
            if (dfs(graph, visited, next)) return true;
        }
        visited[i] = Status.VISITED;
        return false;
    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //graph 생성
        List<List<Integer>> graph = new ArrayList(numCourses);
        for (var i = 0; i < numCourses; i++) {
            graph.add(new ArrayList());
        }
        //graph에 노드, 간선 추가.
        for (var pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
        }
        //cycle 확인을 위해 모든 노드를 순회하며 DFS.
        Status[] visited = new Status[numCourses];
        for (var i = 0; i < numCourses; i++) {
            if (dfs(graph, visited, i)) return false;
        }
        return true;
    }
}

 

레퍼런스

https://leetcode.com/problems/course-schedule/discuss/447754/Java-topological-sort-or-DFS-or-3ms

[Java] topological-sort | DFS | 3ms - LeetCode Discuss