[자바 알고리즘 인터뷰] 12장 그래프 (9) 코스 일정

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

 

 

- 0을 완료하기 위해선느 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다.

- 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라

 

 

풀이 1) DFS로 순환 구조 판별 

 

- 이 문제는 그래프가 순환(Cyclie) 구조인지를 판별하는 문제로 바꿀 수 있다. 

- 순환 구조라면 계속 뱅글뱅글 맴돌게 될 것이고, 해당 코스는 처리할 수 없기 때문이다. 

- 따라서 순환 판별 알고리즘을 구현하면 이 문제를 풀이할 수 있다.

 

Map<Integer,List<Integer>> finishtoTakeMap = new HashMap<>();

//완료하기 위해 처리해야 하는 일정을 finish->take 형태의 그래프로 구성
for(int pre[] : prerequisites)
{
    //값이 존재하지 않을 경우 빈 리스트 생성
    finishtoTakeMap.putIfAbsent(pre[0], new ArrayList<>());
    //처리해야 하는 코스 추가
    finishtoTakeMap.get(pre[0]).add(pre[1]);
}

 

- int prerequisites[][]를 풀어서 [1,0]이라면 1을 완료하기 위해 0을 처리해야 한다는 의미이므로 finishtoTakeMap이라는 이름으로 1->0 형태가 되도록 구성한다. 

 

//처리해야 하는 노드를 저장하는 변수
 ist<Integer> takes = new ArrayList<>();

 /완료해야 하는 노드 순회
 for(Integer finish : finishtoTakeMap.keySet())
 
     /DFS 결과가 fasle라면 최종 결과도 false로 리턴
     if(!dfs(finishtoTakeMap, finish, takes))
     
         return false;
     
 

 /모든 코스에 문제가 없으므로 true 리턴
 return true;

 

- 처리해야 하는 노드를 takes 변수에 저장한다. 

- 순환 구조 여부를 판별하는 문제라고 했으므로, 완료해야 하는 노드가 처리해야 하는 노드, takes에 포함되어 있다면 순환 구조이므로 false를 리턴한다. 

 

public boolean dfs(Map<Integer,List<Integer>>finishtoTakeMap, Integer finish, List<Integer> takes)
{
    //완료해야 하는 노드가 처리해야 하는 노드에 이미 포함되어 있다면
    //그래프가 순환구조이므로 false 리턴
    if(takes.contains(finish))
        return false;
        
    //완료해야 하는 코스에 값이 있다면
    if(finishtoTakeMap.containsKey(finish)) {
        //처리해야 하는 노드에 현재 완료해야 하는 노드 추가
        takes.add(finish);

        //처리해야 하는 노드 순회 
        for(Integer take : finishtoTakeMap.get(finish)) {
            //재귀 DFS, 탐색 결과가 false라면 false를 리턴
            if(!dfs(finishtoTakeMap, take, takes))
                return false;
        }

        //탐색 후에는 처리했으므로 노드 제거
        takes.remove(finish);
    }
    //코스에 문제가 없으므로 true리턴
    return true;

 

- 현재 완료해야 하는 노드가 처리해야 하는 노드를 저장하는 변수 takes에 이미 포함되어 있다면 순환 구조이므로 false를 리턴한다. 

- 한번 false를 리턴하게 되면 계속 상위로 false를 리턴하여 최종 결과도 false를 리턴하게 될 것이다. 

- 탐색은 재귀로 진행하며, 해당 노드를 이용한 모든 탐색이 끝나면 더 이상 처리할 필요가 없으므로 takes.remove(finish)로 노드를 제거하고 리턴한다. 

 

 

class Solution {
    public boolean dfs(Map<Integer,List<Integer>>finishtoTakeMap, Integer finish, List<Integer> takes)
    {
        //완료해야 하는 노드가 처리해야 하는 노드에 이미 포함되어 있다면
        //그래프가 순환구조이므로 false 리턴
        if(takes.contains(finish))
            return false;
        
        //완료해야 하는 코스에 값이 있다면
        if(finishtoTakeMap.containsKey(finish)) {
            //처리해야 하는 노드에 현재 완료해야 하는 노드 추가
            takes.add(finish);

            //처리해야 하는 노드 순회 
            for(Integer take : finishtoTakeMap.get(finish)) {
                //재귀 DFS, 탐색 결과가 false라면 false를 리턴
                if(!dfs(finishtoTakeMap, take, takes))
                    return false;
            }

            //탐색 후에는 처리했으므로 노드 제거
            takes.remove(finish);
        }
        //코스에 문제가 없으므로 true리턴
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer,List<Integer>> finishtoTakeMap = new HashMap<>();

        //완료하기 위해 처리해야 하는 일정을 finish->take 형태의 그래프로 구성
        for(int pre[] : prerequisites)
        {
            //값이 존재하지 않을 경우 빈 리스트 생성
            finishtoTakeMap.putIfAbsent(pre[0], new ArrayList<>());
            //처리해야 하는 코스 추가
            finishtoTakeMap.get(pre[0]).add(pre[1]);
        }

        //처리해야 하는 노드를 저장하는 변수
        List<Integer> takes = new ArrayList<>();

        //완료해야 하는 노드 순회
        for(Integer finish : finishtoTakeMap.keySet())
        {
            //DFS 결과가 fasle라면 최종 결과도 false로 리턴
            if(!dfs(finishtoTakeMap, finish, takes))
            {
                return false;
            }
        }

        //모든 코스에 문제가 없으므로 true 리턴
        return true;
    }
}

 

 

 

풀이 2) 가지치기를 이용한 최적화 

 

- 풀이 1)은 순환이 발견될 때까지 모든 자식 노드를 탐색하는 구조로 되어있다. 

- 순환 여부와 관계없이 만약 복잡하게 서로 호출하는 구조로 그래프가 구성되어 있다면, 불필요하게 동일한 그래프를 여러 번 탐색하게 될 수 있다. 

 

- 이를 개선하여, 최적화가 필요한데, 한 번 방문했던 노드를 두 번 이상 방문하지 않도록 무조건 true를 리턴하는 구조로 개선한다면 탐색 시간을 획기적으로 줄일 수 있을 것이다. 

 

- 처리한 노드를 taken에 삽입하고, 현재 노드가 이미 처리한 노드라면 더 이상 진행하지 않고 true를 리턴한다.

- 또한 탐색을 완료한 후에는 taken,add(finish)로 이미 처리한 노드로 추가한다. 

- 만약 탐색 도중 순환 구조가 발견된다면 false를 리턴하면서 taken에 추가하지 않는 것은 물론, 모든 함수를 빠져나가며 종료하게 될 것이다. 

 

 

class Solution {
    public boolean dfs(Map<Integer,List<Integer>>finishtoTakeMap, Integer finish, List<Integer> takes,List<Integer> taken)
    {
        //완료해야 하는 노드가 처리해야 하는 노드에 이미 포함되어 있다면
        //그래프가 순환구조이므로 false 리턴
        if(takes.contains(finish))
            return false;

        //이미 처리한 노드라면 true 리턴
        if(taken.contains(finish))
            return true;
        
        //완료해야 하는 코스에 값이 있다면
        if(finishtoTakeMap.containsKey(finish)) {
            //처리해야 하는 노드에 현재 완료해야 하는 노드 추가
            takes.add(finish);

            //처리해야 하는 노드 순회 
            for(Integer take : finishtoTakeMap.get(finish)) {
                //재귀 DFS, 탐색 결과가 false라면 false를 리턴
                if(!dfs(finishtoTakeMap, take, takes,taken))
                    return false;
            }

            //탐색 후에는 처리했으므로 노드 제거
            takes.remove(finish);
            //이미 처리한 노드 추가
            taken.add(finish);
        }
        //코스에 문제가 없으므로 true리턴
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer,List<Integer>> finishtoTakeMap = new HashMap<>();

        //완료하기 위해 처리해야 하는 일정을 finish->take 형태의 그래프로 구성
        for(int pre[] : prerequisites)
        {
            //값이 존재하지 않을 경우 빈 리스트 생성
            finishtoTakeMap.putIfAbsent(pre[0], new ArrayList<>());
            //처리해야 하는 코스 추가
            finishtoTakeMap.get(pre[0]).add(pre[1]);
        }

        //처리해야 하는 노드를 저장하는 변수
        List<Integer> takes = new ArrayList<>();
        //처리한 노드를 저장하는 변수
        List<Integer> taken = new ArrayList<>();

        //완료해야 하는 노드 순회
        for(Integer finish : finishtoTakeMap.keySet())
        {
            //DFS 결과가 fasle라면 최종 결과도 false로 리턴
            if(!dfs(finishtoTakeMap, finish, takes,taken))
            {
                return false;
            }
        }

        //모든 코스에 문제가 없으므로 true 리턴
        return true;
    }
}

 

45밀리초