프로그래머스 가장 먼 노드 Java 풀이

풀이

• 해당 문제는 그래프와 그래프 탐색 알고리즘 개념만 알면 상당히 쉬운 문제이다.
• 필자의 풀이는 인접 리스트를 만들어 각 노드가 연결된 노드들을 리스트에 넣어주고(인접리스트) 너비 우선 탐색을 한다.
• 방문하지 않은 노드는 방문을 체크할 배열이 있으므로, 방문시 무조건 처음 방문한게 보장이 되므로 그 노드의 level을 배열에 저장한다.
• 각 노드의 level이 저장된 배열의 max 값을 찾고, max와 같은 레벨의 노드의 갯수를 세면 끝!!

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

        // 그래프 만들기
        // 인접 리스트로 만듬.
        List<List<Integer>> graph = new ArrayList<>();

        // 0번 사용 안함.
        graph.add(new ArrayList<>());

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] node : vertex) {
            int a = node[0];
            int b = node[1];
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        int[] bfs = BFS(graph);
        int max = Arrays.stream(bfs).max().getAsInt();
        answer = (int) Arrays.stream(bfs).filter(v -> v == max).count();

        return answer;
    }

    public int[] BFS(List<List<Integer>> graph) {
        // 여기다 각 노드의 레벨을 저장한다.
        int[] counts = new int[graph.size()];
        int level = 0;
        // 방문 체크할 배열
        boolean[] isVisit = new boolean[graph.size()];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        isVisit[1] = true;
        while (!queue.isEmpty()) {
            int qSize = queue.size();
            for (int i = 0; i < qSize; i++) {
                Integer node = queue.poll();
                List<Integer> nodes = graph.get(node);
                for (int n : nodes) {
                    if (!isVisit[n]) {
                        isVisit[n] = true;
                        queue.offer(n);
                        counts[n] = level + 1;
                    }
                }
            }
            level++;
        }

        return counts;
    }