forked from onlybooks/java-algorithm-interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathP43_2.java
More file actions
61 lines (55 loc) · 2.47 KB
/
P43_2.java
File metadata and controls
61 lines (55 loc) · 2.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package ch12;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class P43_2 {
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 결과가 false라면 최종 결과도 false로 리턴
if (!dfs(finishToTakeMap, finish, takes, taken))
return false;
}
// 모든 코스에 문제가 없으므로 true 리턴
return true;
}
}