FilesExpand file tree

 master

/

1.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (53 loc) · 2.01 KB

 master

/

1.java

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (53 loc) · 2.01 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

62

63

64

import java.util.*;

public class Main {

// 여행지의 개수와 여행 계획에 속한 여행지의 개수

public static int n, m;

public static int[] parent = new int[501]; // 부모 테이블 초기화

// 특정 원소가 속한 집합을 찾기

public static int findParent(int x) {

// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출

if (x == parent[x]) return x;

return parent[x] = findParent(parent[x]);

}

// 두 원소가 속한 집합을 합치기

public static void unionParent(int a, int b) {

a = findParent(a);

b = findParent(b);

if (a < b) parent[b] = a;

else parent[a] = b;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

m = sc.nextInt();

// 부모 테이블상에서, 부모를 자기 자신으로 초기화

for (int i = 1; i <= n; i++) {

parent[i] = i;

}

// Union 연산을 각각 수행

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

int x = sc.nextInt();

if (x == 1) { // 연결된 경우 합집합(Union) 연산 수행

unionParent(i + 1, j + 1);

}

}

}

// 여행 계획 입력받기

ArrayList<Integer> plan = new ArrayList<>();

for (int i = 0; i < m; i++) {

int x = sc.nextInt();

plan.add(x);

}

boolean result = true;

// 여행 계획에 속하는 모든 노드의 루트가 동일한지 확인

for (int i = 0; i < m - 1; i++) {

if (findParent(plan.get(i)) != findParent(plan.get(i + 1))) {

result = false;

}

}

// 여행 계획에 속하는 모든 노드가 서로 연결되어 있는지(루트가 동일한지) 확인

if (result) System.out.println("YES");

else System.out.println("NO");

}

}