<Algorithm> 167. 가장 먼 노드(Programmers)

가장 먼 노드(Programmers)

   사용 알고리즘 :  다익스트라(BFS)

• BFS, DFS 문제만 풀다보니 잊어버릴꺼 같아서 최단경로 문제를 풀어보았다. 쉬운 문제 였지만 확실히 빠릿하게 풀진 못했다... 
• 다풀고 제출했더니 마지막 두 케이스에서 메모리 초과가 발생했다. 처음에 배열로 해보고 싶어서 배열로 만들었더니 그게 문제가 되었다.
• int형 배열은 하나당 4Byte 이므로 최대 4Byte * 50000 * 50000 -> 9.31 GB .... 메모리초과가 무조건 발생할 수 밖에 없었다.

문제에 대한 접근&생각

1. 1번 정점부터 각 정점까지의 최단거리 -> 다익스트라

내 코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue;   public class Solution {    static List<Integer>[] list;    static int[] dist;    static int max;    public static int solution(int n, int[][] edge) {        /******************************         * BFS를 이용해 다익스트라를 구성하여         * 정점 0부터의 각각의 정점까지 최단경로를         * 구한다. 이때 최댓값을 판단하여 그 갯수를         * 출력한다.         *******************************/         list = new ArrayList[n];         for(int i = 0; i < n; i++) list[i] = new ArrayList<>();         for(int i = 0; i < edge.length; i++) {             list[edge[i][0]-1].add(edge[i][1]-1);             list[edge[i][1]-1].add(edge[i][0]-1);         }         dist = new int[n];         Arrays.fill(dist, 9999);         path(n);         int cnt = 0;         for(int i = 0; i < dist.length; i++) {             if(max == dist[i]) cnt++;         }         return cnt;     }        public static void path(int n) {            Queue<Integer> queue = new LinkedList<>();            queue.add(0);            dist[0] = 0;            while (!queue.isEmpty()) {                int vertex = queue.remove();                for(Integer i : list[vertex]) {                    if(dist[i] > dist[vertex]+1 && dist[i] == 9999) {                        dist[i] = dist[vertex]+1;                        queue.add(i);                        max = Math.max(max, dist[i]);                    }                }            }        } }   Colored by Color Scripter

cs

 

얻은 것

• 쉬운 문제라도 문제의 방향을 확실히 정하고 배열을 사용할때 배열의 크기를 한번 더 확인해야 겠다.