Lv 3. 가장 먼 노드

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

프로그래머스

 

 

 

이번 문제는 Dijkstra 기법을 활용하여 

최단거리를 ans[] 배열에 저장하고

최단 거리중 가장 큰값의 갯수를 세어

반환하는 형식으로 풀이하였다.

 

이차원 배열을 통해 node간의 간선 연결정보를

저장하였더니 메모리 초과가 나타나

 ArrayList를 활용하여 간선 연결된 것만 data 저장을

하는 방식으로 풀어내었다.

 

 

 

// 다익스트라 dijkstra algorithm 최단경로 algorithm
// 반대로 가자.
import java.util.*;

class Solution {
    int[] ans;  //최단거리 저장 
    boolean[] isVisited; //들렀나?
    ArrayList<Integer>[] map; 
    class Node{
        int edge;
        int dis;
        public Node(int edge, int dis){
            this.edge = edge;
            this.dis = dis;
        }
    }
    private void BFS(int n){
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(1,0));
        while(!q.isEmpty()){
            Node now = q.poll();
            if(isVisited[now.edge]) continue; // 만약 최단경로아니고 이미들른곳이면 pass
            isVisited[now.edge] = true;
            ans[now.edge] = now.dis;
            for(int i : map[now.edge]){
                if((now.dis+1) < ans[i])
                    q.add(new Node(i,now.dis+1));
            }
        }
    }
    //최대 경로 갯수 몇개 
    private int findAnswer(int n){
        int maxValue = Integer.MIN_VALUE;
        int result = 0;
        for(int i = 1 ; i < n ; i++){
            if(maxValue < ans[i]){
                result = 1;
                maxValue = ans[i];
            }else if( maxValue == ans[i]) result++;
            
        }
        return result;
    }
    public int solution(int n, int[][] edge) {
        ans = new int[n+1];
        isVisited = new boolean[n+1];
        map = new ArrayList[n+1];
        //초기화
        Arrays.fill(ans,Integer.MAX_VALUE);
        for(int i = 1 ; i <= n ; i++)
            map[i] = new ArrayList<>();
        for(int[] connect : edge){
            map[connect[0]].add(connect[1]);
            map[connect[1]].add(connect[0]);
        }
        BFS(n+1);
        return findAnswer(n+1);
    }
}

// 메모리초과 이차원배열을 arraylist로