문제

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

0에서 n-1까지 레이블이 붙여진 총 n 개의 과정이 있습니다.

예를 들어 코스 0을 수강하기 위해 일부 코스에는 전제 조건이있을 수 있습니다. 먼저 코스 1을 수강해야합니다. [0,1]

총 과정 수와 전제 조건 쌍이 주어지면 모든 과정을 마칠 수 있습니까?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.
총 2 개의 코스가 있습니다.
1 코스를 수강하려면 0 코스를 마쳤어야합니다. 
따라서 가능합니다.

Exapmple 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.
총 2 개의 코스가 있습니다. 
과정 1을 수강하려면 과정 0을 마쳐야 하고 과정 0을 마치려면 마찬가지로 과정 1을 마쳐야 합니다. 
따라서 불가능합니다.

Note :

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

기본 지식

큐(Queue)

컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식

• add(item), offer(item): item을 리스트의 끝부분에 추가한다.
• remove(), poll(): 리스트의 첫 번째 항목을 제거한다.
• peek(): 큐에서 가장 위에 있는 항목을 반환한다.
• isEmpty(): 큐가 비어 있을 때에 true를 반환한다.

풀이

이번 문제는 “위상 정렬”이란 알고리즘 기법이고 위상 정렬(Topological Sort)이란 블로그에 잘 정리되어 있어 참고 부탁드립니다.

문제의 핵심은

1. indegree == 0 인 것을 탐색
2. 그 노드와 관련된 edge(선) 제거, indegree 업데이트
3. 1,2를 반복
4. 모든 반복을 끝으로 정렬 완료

Note : indegree는 노드로 들어오는 선의 갯수입니다.

0,1은 indegree가 0개 이며, 2,4는 1개, 3,5는 3개 입니다.

위상 정렬은 위와 같은 방식으로 진행하며 위의 문제는 모든 과정을 마칠 수 있는지 true, false로 결과값이 나와야 하므로, 모든 반복이 끝난 후, 모든 노드가 탐색 되었는 지 확인 후 하나라도 존재 한다면 불가능 하므로 false값을 리턴하고, 없으면 true를 리턴하면 됩니다.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> adjList = new ArrayList<>();
        for(int i=0; i<numCourses; i++) adjList.add(new ArrayList<Integer>());
        
        for(int[] edge: prerequisites ){
            indegree[edge[0]]++;
            adjList.get(edge[1]).add(edge[0]);
        }

        // 1. 그래프 초기화 
        Queue<Integer> q = new LinkedList<>();

        for(int i=0; i<numCourses; i++){
            if(indegree[i]==0) q.offer(i);
        }
        // 2. indegree 0인 노드 큐에 추가 

        Set<Integer> visited = new HashSet<>();
        // 나중에 비교하기 위한 방문한 노드 리스트

        while(!q.isEmpty()){
            int node = q.poll();
            visited.add(node);
            for(int dest: adjList.get(node)){
             if(--indegree[dest] == 0) q.offer(dest);   
             // indegree == 0 인 노드 탐색
            }
            adjList.get(node).clear();
            // 선 제거
        }
        // 3. 반복문

        return visited.size()==numCourses;
        // 방문한 노드 갯수와 과정 갯수가 일치하면
        // 모든 노드를 탐색했다는 뜻
    }
}

Note : prerequisites에서 [0,1]의 뜻은 0 과정을 들으려면 1 과정을 들어야 한다는 뜻입니다

1 그래프 초기화 과정을 설명 드리면 indegree[edge[0]]++ 해당 과정(노드)의 코스(조건 쌍)가 있으면 indegree를 증가시켜 각 indegree를 측정합니다. 그리고 adjList.get(edge[1]).add(edge[0]) 로 과정의 선수 과정을 기록하는 것입니다. ( 반대로 outdegree를 기록 )

즉, 이 과정을 마치면 이런식으로 될 것입니다. ( 위의 그림을 예로 설명하겠습니다.)

indegree[0] : 0
indegree[1] : 0
indegree[2] : 1
indegree[3] : 3
indegree[4] : 1
indegree[5] : 3
5는 2,3,4를 선수과정으로 수행해야 하므로 
prerequisites에 [5,2] [5,3] [5,4]
위와 같이 주어 졌을 것입니다.

Note : indegree[과정 번호] : indegree 갯수

adjList 0  List [2,3]
        1  List [3,4] 
        2  List [3,5]
        3  List [5]
        4  List [5]
        5

Note : adjList 과정 번호 List [outdegree 과정 번호]

초기화 후 indegree == 0 인 노드를 큐에 offer합니다.

queue : 0, 1

반복문 첫번째 루프에 진입하면

q.poll() 로 0을 가지고 옵니다.

queue : 1

for(int dest: adjList.get(node)){
    if(--indegree[dest] == 0) q.offer(dest);
}

adjList.get(0)은 List [2,3] 이므로 dest = 2로 반복문이 실행되고 --indegree[2] = 1 - 1 = 0 if문이 실행 되므로 q.offer(2)

queue : 1 2

dest = 3 --indegree[3] = 3 - 1 = 2 if문 패스

다음 반복루프 q.poll()로 1을 가져옵니다.

queue : 2

adjList.get(1)은 List [3,4], dest = 3 --indegree[3] = 2 - 1 = 1, if문 패스

dest = 4 --indegree[4] = 1 - 1 = 0, q.offer(4)

queue : 2 4

다음 반복루프 q.poll()로 2을 가져옵니다.

queue : 4

adjList.get(2)은 List [3,5], dest = 3 --indegree[3] = 1 - 1 = 0, q.offer(3)

queue : 4 3

dest = 5 --indegree[5] = 3 - 1 = 2, if문 패스

다음 반복루프 q.poll()로 4을 가져옵니다.

queue : 3

adjList.get(4)은 List [5], dest = 5 --indegree[5] = 2 - 1 = 1, if문 패스

다음 반복루프 q.poll()로 3을 가져옵니다.

queue : 

adjList.get(3)은 List [5], dest = 5 --indegree[5] = 1 - 1 = 0, q.offer(5)

queue : 5

다음 반복루프 q.poll()로 5을 가져옵니다.

queue : 

adjList.get(5)은 List가 없고 이렇게 반복문이 종료됩니다.

이렇게 indegree[0,1,2,3,4,5]는 모두 0이 되고( 주어진 prerequisites에 대해서 다 방문했다는 뜻), visited에 방문한 노드가 리스트로 저장되어 있습니다.

방문한 노드의 수와 과목 갯수가 같으면 과정을 정상적으로 이수하는 것이 가능합니다.

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상