[JAVA] 프로그래머스 : 가장 먼 노드 (코딩테스트 고득점 kit > 그래프)

https://programmers.co.kr/learn/courses/30/lessons/49189?language=java

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

처음에 간선 간의 가중치를 1로 생각하여 다익스트라그램을 이용하여 최단 경로를 구한다음 가장 먼 거리에 있는 것들을 찾았는데 테스트케이스 9, 10 에서 시간이 넘어갔다.

그래서 BFS를 이용하여 구현하였다.

해결방안

1. BFS를 이용하였으며 각각 vertex들과 start의 거리를 distance에 배열에 저장해줌

2. distance 배열에 저장되어있는 것들 중 가장 먼 vertex들의 거리를 farthestDepth에 저장하고 distance 배열에서 farthesDepth 인 것들을 찾아 갯수를 세줌

 

코드

import java.util.*;

// 가장 먼 노드
class Solution {
    
    public static boolean[] visited;
    public static int[] distance;
    public static ArrayList<ArrayList<Integer>> graph;
    public static int cnt;
    public static int farthestDepth;
    
    public static void bfs(){
        cnt = 0;
        farthestDepth = 0;
        int start = 1;
        
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        
        int current;
        int near;
        while(!q.isEmpty()){
            current = q.poll();
            
            // 인접 노드 다 찾기
            for(int i=0; i<graph.get(current).size(); i++){
                near = graph.get(current).get(i);
                
                if(!visited[near]){
                    distance[near] = distance[current]+1;
                    q.offer(near);
                    visited[near] = true;
                }
            }
        }
        
        for(int i=1; i<distance.length; i++){
            farthestDepth = Math.max(farthestDepth, distance[i]);
        }
        
        for(int i=1; i<distance.length; i++){
            if(distance[i]==farthestDepth)
                cnt++;
        }

    }
    
    public int solution(int n, int[][] edge) {
        
        visited = new boolean[n+1];
        distance = new int[n+1];
        graph = new ArrayList<>();
        
        for(int i=0; i<n+1; i++){
            graph.add(new ArrayList<Integer>());
        }
        
        int vertex1;
        int vertex2;
        for(int i=0; i<edge.length; i++){
            vertex1 = edge[i][0];
            vertex2 = edge[i][1];
            
            graph.get(vertex1).add(vertex2);
            graph.get(vertex2).add(vertex1);
        }
    
        
        bfs();
        
        return cnt;
    }
}