풀이 방법
노드 별 최단 경로를 구하기 위해 Node 클래스를 만들어서 노드 번호와 1번에서 해당 노드까지의 길이를 가지도록 했다.
bfs 를 이용해서 노드까지의 길이를 비교해서 최댓값일 경우 cnt를 증가시켜주었다.
내 코드
import java.util.*;
class Solution {
public int solution(int n, int[][] edge) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
boolean[] visited = new boolean[n + 1];
for(int i = 0; i <= n; i++){
list.add(new ArrayList<Integer>());
}
for(int i = 0; i < edge.length ;i++){
list.get(edge[i][0]).add(edge[i][1]);
list.get(edge[i][1]).add(edge[i][0]);
}
Queue<Node> q = new LinkedList<>();
q.add(new Node(1, 0));
int cnt = 0;
int max = 0;
while(!q.isEmpty()){
Node node = q.poll();
if(visited[node.index])
continue;
if(max < node.len){
cnt = 1;
max = node.len;
} else if(max == node.len) {
cnt++;
}
visited[node.index] = true;
for(int i = 0; i < list.get(node.index).size(); i++){
q.add(new Node(list.get(node.index).get(i), node.len + 1));
}
}
System.out.println(cnt);
return cnt;
}
class Node{
int index;
int len;
Node(int index, int len){
this.index = index;
this.len = len;
}
}
}
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
N으로 표현 (0) | 2021.11.19 |
---|---|
피로도 (0) | 2021.10.26 |
순위 (0) | 2021.10.22 |
추석 트래픽 (0) | 2021.10.21 |
아이템 줍기 (0) | 2021.10.20 |