그래프 - 가장 먼 노드

프로그래머스 (그래프) - 가장 먼 노드

해당 문제는 BFS 알고리즘을 활용해서 푸는 문제였습니다. 최상단 1번노드 부터 시작하여 1번 노드까지의 길이를 1로 시작하여 해당 노드와 연결된 다른 노드들의 정보를 큐에 넣고, 미리 만들어둔 해당 노드까지의 길이를 저장하는 배열에 현재노드까지의 길이 + 1의 값을 저장해 둡니다. edge의 좌우 순서가 중요하지 않으므로 연결 노드를 잘 찾아야 했습니다.

public int solution(int n, int[][] edge) {
        int answer = 0;

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

        Queue<Integer> bfsQueue = new LinkedList<>();
        bfsQueue.add(1);

        while (!bfsQueue.isEmpty()) {
            int currentNode = bfsQueue.poll();

            for (int i = 0; i < edge.length; i++) {
                if (currentNode == edge[i][0] && nodeLengths[edge[i][1]] == 0) {
                    nodeLengths[edge[i][1]] = nodeLengths[currentNode] + 1;
                    bfsQueue.add(edge[i][1]);
                }
                if (currentNode == edge[i][1] && nodeLengths[edge[i][0]] == 0) {
                    nodeLengths[edge[i][0]] = nodeLengths[currentNode] + 1;
                    bfsQueue.add(edge[i][0]);
                }
            }
        }

        Arrays.sort(nodeLengths);
        int max = nodeLengths[nodeLengths.length - 1];

        for (int i = n; i >= 0; i--) {
            if (nodeLengths[i] < max) {
                break;
            }
            answer++;
        }

        return answer;
    }