[고득점 Kit - 그래프] 가장 먼 노드

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

프로그래머스

 

문제 유형

• 다익스트라

 

문제 난이도

• Lev 3

 

문제 분석

해당 문제는 전형적인 그래프 유형 중 다익스트라 문제이다. Queue와 dist[] 배열을 사용해서, 노드간의 최단 경로를 찾아주면 되는 기본 문제로 다른 설명은 필요 없을 것 같다.

 

전체 코드

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        List<Integer>[] graph = new List[n+1];
        for(int i = 0; i < n+1; i++) graph[i] = new ArrayList<>();
        
        // 그래프간의 간선 연결
        int a, b;
        for(int i = 0; i < edge.length; i++) {
            a = edge[i][0];
            b = edge[i][1];
            
            graph[a].add(b);
            graph[b].add(a);
        }
        
        int[] dist = new int[n+1];
        Arrays.fill(dist, 50001);
        
        ArrayDeque<int[]> q = new ArrayDeque<>();
        
        q.offer(new int[]{1, 0});
        dist[1] = 0;
        
        while(!q.isEmpty()) {
            
            int[] p = q.poll();
            
            for(Integer next : graph[p[0]]) {
                if(dist[next] > p[1] + 1) {
                    q.offer(new int[]{next, p[1] + 1});
                    dist[next] = p[1] + 1;
                }   
            }   
        }
        
        int max = -1;
        
        for(int i = 1; i < n+1; i++) {
            if(dist[i] > max) max = dist[i];
        }
        
        for(int i = 1; i < n + 1; i++) {
            if(dist[i] == 50001) continue;
            if(max == dist[i]) answer++;
        }
        
        return answer;
    }
}