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

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

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

2021-08-30

---

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
       int answer = 1;
        int[] dist = new int[n+1];
        List<List<Integer>> list = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        boolean[] vtd = new boolean[n+1];
 
        for(int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
            dist[i] = 987654321;
        }
 
        for(int i = 0; i < edge.length; i++) {
            list.get(edge[i][0]).add(edge[i][1]);
            list.get(edge[i][1]).add(edge[i][0]);
        }
 
        q.add(1);
        dist[0] = 0;
        dist[1] = 0;
        while(!q.isEmpty()) {
            int tmp = q.poll();
            if(vtd[tmp]) continue;
            vtd[tmp] = true;
            for(int val: list.get(tmp)) {
                if(dist[val] > dist[tmp] + 1) {
                    dist[val] = dist[tmp] + 1;
                    q.add(val);
                }
            }
        }
        Arrays.sort(dist);
        int value = dist[dist.length - 1];
        for(int i = dist.length - 2; i >= 0; i--) {
            if(value == dist[i]) answer++;
            else break;
        }
 
        return answer;
    }
}

#문제풀이

각 노드별로의 최단 경로를 구하는 문제지만, 가중치가 없어서 다익스트라 말고 bfs로 풀었다.

 

dist배열 만들어서 최단 경로 계속 갱신 해준 후, 가장 큰 값들의 갯수를 카운팅 했다.