207. Course Schedule

문제

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

• 문제 의도는 사이클이 존재하는지 확인하는 것이다.
• prerequisites[i] = [ai, bi] : bi는 ai보다 먼저 수강해야 함을 나타내는 필수 조건 배열

• 링크: https://leetcode.com/problems/course-schedule/description/

Solution

class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        // 사이클이 없음을 검증한 노드들을 추적
        boolean[] finish = new boolean[numCourses];
        // 현재 DFS 탐색 중에 방문한 노드를 추적하여 사이클을 감지
        boolean[] visiting = new boolean[numCourses];

        // 인접 리스트로 그래프를 초기화하여 각 강좌 간의 의존성을 나타냄
        List<Integer>[] graph = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }

        // prerequisites에서 그래프를 생성, 각 방향 간선은 의존성을 나타냄
        for (int[] prerequistite : prerequisites) {
            int cur = prerequistite[0];
            int pre = prerequistite[1];
            graph[pre].add(cur);
        }

        // 모든 강좌에 대해 DFS 수행; 사이클이 감지되면 false 반환
        for (int start = 0; start < numCourses; start++) {
             if (!dfsCanFinish(graph, finish, visiting, start)) return false;
        }
        return true;
    }

    // DFS 탐색을 위한 헬퍼 메서드로, 그래프에서 사이클을 감지
    public boolean dfsCanFinish(List<Integer>[] graph, boolean[] finish, boolean[] visiting, int start) {

        // 현재 노드가 DFS 스택에 있으면 사이클이 발생한 것
        if (visiting[start]) return false;
        // 이 노드를 이미 처리한 적이 있다면, 이 경로에는 사이클이 없음
        if (finish[start]) return true;

        // DFS 스택에 현재 노드를 방문 중으로 표시
        visiting[start] = true;
        // 인접한 모든 노드(의존 강좌) 재귀적으로 처리
        for (int next : graph[start]) {
            // 의존 강좌 중 하나라도 사이클이 있으면 실패를 반환
            if (!dfsCanFinish(graph, finish, visiting, next)) return false;
        }

        // 노드 처리 완료 후 방문 상태 해제
        visiting[start] = false;
        // 이 노드가 속한 경로에 사이클이 없음을 표시
        finish[start] = true;

        return true;
    }
}

사이클을 찾는 문제였다. 탐색 중 방문하고 있음을 표시하는 visiting, 탐색 검증이 끝난 노드를 관리하는 finish 배열을 사용하여 사이클 여부를 파악하였다. 각 노드를 시작점으로 탐색(dfs)하지만 이미 한번 탐색해서 사이클이 없음을 검증한 노드는 탐색하지 않고 true를 반환한다.

주의

        List<Integer>[] graph = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();  // 각 요소에 새로운 ArrayList 객체를 생성
        }
        
                // 그래프 초기화
        for(int[] prerequistite : prerequisites) {
            int cur = prerequistite[0];
            int pre = prerequistite[1];
            graph[pre].add(cur);
        }

그래프를 초기화하는 과정에서 어려움을 겪었다. 이전 코드는 다음과 같다.

        List<Integer>[] graph = new ArrayList[numCourses];
        Arrays.fill(graph, new ArrayList<>());
        
                // 그래프 초기화
        for(int[] prerequistite : prerequisites) {
            int cur = prerequistite[0];
            int pre = prerequistite[1];
            graph[pre].add(cur);
        }

각 요소에 빈 배열을 추가하기 위해 Arrays.fill(array, new Object())를 사용했으나, 이 방법은 배열의 모든 요소가 동일한 객체를 참조하게 만듭니다.

본래 의도는 각 요소에 독립적인 빈 배열을 할당하는 것이었지만, Arrays.fill(array, new Object())로 초기화할 경우 모든 요소가 동일한 객체를 참조하므로, 한 요소의 값을 변경하면 다른 요소에도 동일한 변경이 적용됩니다.

가변 객체 초기화 시 

참조

링크: https://lahezy.tistory.com/m/117

자바 객체 복사 방법(얕은 복사, 깊은 복사)

 

링크: https://www.youtube.com/watch?v=bG9IObCN-tg