[프로그래머스/Level3] 가장 먼 노드

문제 링크: 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();
    }
}