문제 링크: https://programmers.co.kr/learn/courses/30/lessons/49189
해당 문제는 BFS
를 이용하여 1번 노드부터 각 노드까지의 거리를 갱신하는 문제이다.
BFS
를 수행하며 노드의 거리를 갱신해주는데, 이미 거리가 갱신되었던 노드는 해주면 안된다.
모든 노드를 방문했으면, 거리 배열에서 최대 거리와 같은 원소가 몇 개인지 카운트하면 끝.
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
class Solution {
public int solution(int n, int[][] edge) {
int[] distance = new int[n + 1];
boolean[] visit = new boolean[n + 1];
int maxDistance = 0;
Queue<Integer> q = new LinkedList<>();
q.add(1);
while (!q.isEmpty()) {
int curIdx = q.poll();
if (!visit[curIdx]) {
visit[curIdx] = true;
for (int[] e : edge) {
int childIdx;
if (e[0] == curIdx || e[1] == curIdx) {
if (e[0] == curIdx) {
childIdx = e[1];
} else {
childIdx = e[0];
}
if (!visit[childIdx]) {
if (distance[childIdx] == 0) {
distance[childIdx] = distance[curIdx] + 1;
maxDistance = Math.max(distance[childIdx], maxDistance);
}
q.add(childIdx);
}
}
}
}
}
int finalMaxDistance = maxDistance;
return (int) Arrays.stream(distance).filter(i -> i == finalMaxDistance).count();
}
}