가장 먼 노드 (그래프)

원본 : https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

풀이

import java.util.*;

class Solution {
    public static boolean[] visited;
    public static boolean[][] graph;
    public static Queue<int[]> queue;
    public static List<int[]> nodeList;

    public int solution(int n, int[][] edge) {
        visited = new boolean[n + 1];
        graph = new boolean[n + 1][n + 1];
        queue = new LinkedList<>();
        nodeList = new ArrayList<>();

        for (int[] ij : edge) {
            graph[ij[0]][ij[1]] = true;
            graph[ij[1]][ij[0]] = true;
        }

        visited[1] = true;
        queue.add(new int[]{1, 1});

        bfs();

        int max = nodeList.get(nodeList.size() - 1)[1];
        int cnt = 0;

        for (int i = nodeList.size() - 1; i >= 0; i--) {
            if (nodeList.get(i)[1] == max) {
                cnt++;
            } else {
                break;
            }
        }

        return cnt;
    }

    public void bfs() {
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            nodeList.add(node);

            for (int i = 0; i < visited.length; i++) {
                if (!visited[i] && graph[node[0]][i]) {
                    visited[i] = true;
                    queue.add(new int[]{i, node[1] + 1});
                }
            }
        }
    }
}