FilesExpand file tree

 master

/

Programmers1.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

61 lines (49 loc) · 1.56 KB

 master

/

Programmers1.java

Top

File metadata and controls

• Code
• Blame

61 lines (49 loc) · 1.56 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

import java.util.*;

/*

* Programmer 가장 먼 노드

* BFS로 풀어야 될것으로 보임

* */

class Solution {

public int solution(int n, int[][] edge) {

int answer = 1;

Map<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>(); // 그래프

int[] degree = new int[n + 1];

boolean[] visited = new boolean[n + 1]; // 방문 여부

// 그래프 세팅

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

graph.put(i ,new ArrayList<Integer>());

}

for (int i = 0; i < edge.length; i++) {

ArrayList<Integer> v1 = graph.get(edge[i][0]);

ArrayList<Integer> v2 = graph.get(edge[i][1]);

if (!v1.contains(edge[i][1])) v1.add(edge[i][1]);

if (!v2.contains(edge[i][0])) v2.add(edge[i][0]);

}

Queue<Integer> q = new LinkedList<Integer>();

// 노드 1 부터 시작

q.offer(1);

visited[1] = true;

// BFS

while (!q.isEmpty()) {

int v = q.poll();

for (int i : graph.get(v)) {

if (!visited[i]) {

degree[i] = degree[v] + 1;

visited[i] = true;

q.offer(i);

}

}

}

// 가장 멀리 있는 노드 개수

int max = 0;

for (int i : degree) {

if (max < i) {

answer = 1;

max = i;

} else if (max == i) {

answer++;

}

}

return answer;

}

}