[LeetCode] 207.Course Schedule(다시 풀어보자!)
[LeetCode] 207.Course Schedule 👏새로운개념
문제 이해하기
(00:90 해결x -> 개념 찾아봄..)
numCourses 개 만큼의 코스가 존재한다. 0 ~ numCourses-1 의 라벨이 매겨져 있다.
prerequisites[i] 는 int[2] 짜리 배열로, prerequisites[i][1] 은 prerequisites[i][0] 인 과목의 선수과목이다. 즉, prerequisites[i][1] 을 들어야만 prerequisites[i][0] 을 수강할 수 있다.
이러한 정보들이 주어질 때, 모든 코스를 끝낼 수 있다면 true를 리턴, 그렇지 않으면 false를 리턴하라.
이 문제는 왠지 문제 이해가 핵심인 것 같다.
- 모든 과목을 들을 수 있는지 확인하기 위해 count를 하거나
- visit을 만들던가 해야할 것 같다
예시2는 마치 데드락과 같은 상황... 서로가 선수조건으로 서로를 원하고 있음
- 즉, 불가능한 경우 ? → cycle이 생기는 경우
- 이 문제는 unique한 prerequisite 만을 준다고 하였음
문제 풀이 ( 새로운 개념 )
단방향 그래프에서 싸이클을 찾아야 하는 상황이다.
이 문제는 하나하나에 대해 dfs를 한다면 시간초과가 나올 것이다.
- 그럼 어떻게 풀어야하지?? 단방향 그래프에서 싸이클이 생겨나는 것을 어떻게 알 수 있을까? 기존에 유니온 파인드 방식으로 해 보려니, 이는 합집합을 구하는 거라 상황에 맞지 않는 듯 했다. ( 양방향또는 무방향 그래프일 때 적용.. )
그래프에서 DFS로 싸이클 찾기
- 모든 노드에서 dfs를 하며 자기자신에게 오는지 확이하는 것은 백프로 시간초과였다.
- dfs 를 사용하여 재귀적으로 그래프의 노드들을 타고 흘러가기 때문에 이 방식을 사용할 수 있다.
- 즉, dfs 를 통해 x 노드를 방문
- 해당 노드가 이미 방문 되었음 && 그런데 이 노드를 거쳐간 dfs 함수가 아직 호출종료 되지 않음 ( 그럼에도 다시 이 노드를 방문했다는 것은 → cycle이 존재한다는 의미와 같음 )
- 즉, dfs 를 통해 x 노드를 방문
- 따라서 이 과정을 위해
-
노드의 방문여부를 확인하는 테이블
-
함수의 종료 여부를 확인하는 테이블
-
둘 다 false로 초기화 시켜놓는것
이 필요하다.
-
class Solution {
// 인접 리스트 그래프
public ArrayList<Integer>[] graph = new ArrayList[100001];
// 방문 여부
public boolean[] visit;
// 함수 호출 종료 여부
public boolean[] finish;
// 싸이클 존재여부
public boolean cycle;
public boolean canFinish(int numCourses, int[][] prerequisites) {
// init table
visit = new boolean[numCourses];
finish = new boolean[numCourses];
//===== init graph ====
for(int i=0;i < numCourses ; i++)
graph[i] = new ArrayList<Integer>();
// prerequisites[i][0] 의 부모노드 prerequisites[i][1]
for(int[] c:prerequisites){
graph[c[0]].add(c[1]);
}
// 일단 모든 노드를 시작으로 한다
for(int i =0 ;i<numCourses;i++){
dfs(i);
if(cycle) break;
}
// cycle이 존재함 -> 끝낼 수 없음
// cycle이 존재하지 않음 -> 끝낼 수 있음
return !cycle;
}
// cur 노드를 방문
public void dfs(int cur){
if(visit[cur]){
// 이미 이 cur을 다녀간 dfs 함수가 아직 진행중 ( 인데 또 방문했다는 것은 cycle이 존재함을 뜻함)
if(!finish[cur])cycle = true;
// 중복 방문은 안되니까 (기하급수적으로 늘어나버림 )
return;
}
visit[cur] = true;
// 인접 노드들을 방문
for(Integer adj : graph[cur]){
dfs(adj);
}
finish[cur] = true;
}
}
🚀 DFS와 cycle
dfs를 사용하여 cycle여부 확인이 가능함을 새로 알게되었음 - dfs 를 사용하며 가지치기만 잘 하면 거의 O(V+E) 로 문제를 푸는게 가능하다
Author And Source
이 문제에 관하여([LeetCode] 207.Course Schedule(다시 풀어보자!)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/LeetCode-207.Course-Schedule저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)