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

 

programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

로직

BFS를 이용하여 1에서 각 노드까지의 최단거리들을 구하고 그 중 가장 긴 거리를 가진 노드 개수를 카운트하여 리턴해주었다.

코드

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        int[] distances = new int[n+1];
        distances[1] = 1;
        Hashtable<Integer, LinkedList<Integer>> edgeInfo = new Hashtable<Integer, LinkedList<Integer>>(n);
    	// initialize hash table
        for(int i = 1;i<n + 1; i++){
            edgeInfo.putIfAbsent(i, new LinkedList<Integer>());
        }
        // make the edge info
        for(int[] vertice : edge){
            int vertex1 = vertice[0];
            int vertex2 = vertice[1];
            LinkedList<Integer> vertex1_list = edgeInfo.get(vertex1);
            vertex1_list.add(vertex2);
            LinkedList<Integer> vertex2_list = edgeInfo.get(vertex2);
            vertex2_list.add(vertex1);
        }
       
        // start bf searching
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(1);
        int maxDist = 1;
        
        while(queue.peek() != null){
            int node = queue.poll();
            Iterator itr = edgeInfo.get(node).iterator();
            while(itr.hasNext()){
                int child = (int) itr.next();
                if(distances[child] == 0){
                    queue.offer(child);
                    distances[child] = distances[node] + 1;
                    maxDist = Math.max(distances[child], maxDist);
                }
            }
        }
        int answer = 0;
        
        // find max node
        for(int i =1; i< n + 1; i++){
            if(distances[i] == maxDist){
                answer += 1;
            }
        }
        
        return answer;
    }
    
    void printLinkedList(LinkedList<Integer> linkedList){
        for(Integer i : linkedList){
            System.out.print(" " + i);
        }
        System.out.println(" ");
    }
}