FilesExpand file tree

 main

/

P43_2.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

61 lines (55 loc) · 2.47 KB

 main

/

P43_2.java

Copy path

Top

File metadata and controls

• Code
• Blame

61 lines (55 loc) · 2.47 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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;

}

}