리트코드) 207. 코스 일정 (자바)

문제 : n개의 코스가 주어지고, 쌍으로 된 코스가 주어진다.
코스를 수강하려면 먼저 수강 해야 함 을 나타내는 prerequisites배열 이 제공된다. 모든 코스가 완료 가능한지 판별하라.

입력1: numCourses = 2, 전제 조건 = [[1,0]] 출력: true 설명: 총 2개 과정을 수강해야 하며, 1과정을 수강하려면 0과정을 이수해야 하므로 가능합니다.

입력2 : numCourses = 2, 전제 조건 = [[1,0],[0,1]] 출력: false 설명: 총 2개 과정을 수강해야 하며, 1과목을 수강하려면 0과목을 이수해야 하고, 0과목을 수강하려면 1과목도 이수해야 하기 때문에 불가능

• 순환구조인지 판별하는 문제(순환구조이면 뱅글뱅글 돌아서 처리할 수 없음)

mport java.util.*;
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, ArrayList<Integer>> preMap = new HashMap<>();
        for(int i=0; i<prerequisites.length; i++) {
            preMap.putIfAbsent(prerequisites[i][0], new ArrayList<>()); // key가 없으면 저장(빈값으로)하라
            preMap.get(prerequisites[i][0]).add(prerequisites[i][1]); // key로 가져와서 값 더하기

        }
        // 처리해야하는 노드를 저장하는 변수
        List<Integer> takes = new ArrayList<>();
        // 완료해야하는 노드 순회
        for(Integer key : preMap.keySet()) {
            if(!dfs(preMap, key, takes)) {
                return false;
            }
        }
        // 순환구조가 아니어서 코스를 이행할 수 있음
        return true;
    }

    public boolean dfs(Map<Integer, ArrayList<Integer>> preMap, Integer key, List<Integer> takes) {
        // 순환구조이므로 false 반환
        if(takes.contains(key)) {
            return false;
        }

        // 완료해야하는 코스에 값이 있다면
        if(preMap.containsKey(key)) {
            // 처리해야하는 노드에 추가
            takes.add(key);

            for(Integer take : preMap.get(key)) {
                if(!dfs(preMap, take, takes)) {
                    return false;
                }
            }
            takes.remove(key);
        }
        return true;
    }
}

Time Limit Exceeded

• 시간초과 되므로 방문한 것은 다시 실행되지 않도록 최적화 한다.

  import java.util.*;
  class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, ArrayList<Integer>> preMap = new HashMap<>();
        for(int i=0; i<prerequisites.length; i++) {
            preMap.putIfAbsent(prerequisites[i][0], new ArrayList<>()); // key가 없으면 저장(빈값으로)하라
            preMap.get(prerequisites[i][0]).add(prerequisites[i][1]); // key로 가져와서 값 더하기
  
        }
        // 처리해야하는 노드를 저장하는 변수
        List<Integer> takes = new ArrayList<>();
        // 처리한 노드를 저장하는 변수(visited)
        List<Integer> taken = new ArrayList<>();
        // 완료해야하는 노드 순회
        for(Integer key : preMap.keySet()) {
            if(!dfs(preMap, key, takes, taken)) {
                return false;
            }
        }
        // 순환구조가 아니어서 코스를 이행할 수 있음
        return true;
    }
  
    public boolean dfs(Map<Integer, ArrayList<Integer>> preMap, Integer key, List<Integer> takes, List<Integer> taken) {
        // 순환구조이므로 false 반환
        if(takes.contains(key)) {
            return false;
        }
        // 순환구조이므로 false 반환
        if(taken.contains(key)) {
            return true;
        }
        // 완료해야하는 코스에 값이 있다면
        if(preMap.containsKey(key)) {
            // 처리해야하는 노드에 추가
            takes.add(key);
  
            for(Integer take : preMap.get(key)) {
                if(!dfs(preMap, take, takes, taken)) {
                    return false;
                }
            }
            takes.remove(key);
            taken.add(key); // visited
        }
        return true;
    }
  }
  

참고 도서 : 자바 알고리즘 인터뷰 with 코틀린 459p