프로그래머스 가장 먼 노드

가장 먼 노드 Java 

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

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

 

풀이

최단 경로 알고리즘인 다익스트라 알고리즘을 사용했다.

각 노드의 최단경로로 인접 노드를 방문하며 cost를 구해 가장 큰 값을 가진 노드들을 카운트 하는 방법으로 해결했다.

우선순위큐를 사용하여 인접노드를 방문하기까지의 cost를 구했기 때문에 최단거리를 보장받을 수 있다.

 

public static class Node implements Comparable<Node> {
    int index;
    int cost;
    ArrayList<Integer> edge = new ArrayList<>();

    public Node(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }

    public void addEdge(int edge) {
        this.edge.add(edge);
    }

    @Override
    public int compareTo(Node node) {
        if (this.cost > node.cost) return 1;
        else return 0;
    }
}

public static int solution(int n, int[][] edge) {
    ArrayList<Node> ar = new ArrayList<>();
    for (int i=0; i<=n; i++) {
        ar.add(new Node(i, 0));
    }
    for (int[] item : edge) {
        int nodeIndex = item[0];
        int nodeEdge = item[1];
        ar.get(nodeIndex).addEdge(nodeEdge);
        ar.get(nodeEdge).addEdge(nodeIndex);
    }

    int maxCost = dijkstra(ar, n);
    int answer = 0;
    for (int i=1; i<=n; i++) {
        if (ar.get(i).cost == maxCost) answer+=1;
    }
    return answer;
}

public static int dijkstra(ArrayList<Node> ar, int n) {
    PriorityQueue<Node> pq = new PriorityQueue<>(); //우선순위 큐
    boolean[] visit = new boolean[n+1]; //방문체크
    pq.add(ar.get(1));
    int maxCost = 0; //해당 변수의 값을 갱신해주며 최대 값을 저장한다.
    while (!pq.isEmpty()) {
        Node me = pq.poll();
        if (visit[me.index]) continue; //중복된 방문을 방지한다.
        visit[me.index] = true; //방문한 노드는 방문처리를 한다.
        ar.get(me.index).cost = me.cost; 
        maxCost = Math.max(maxCost, me.cost);
        for (int edgeIndex : me.edge) {
            if (visit[edgeIndex]) continue; //방문한 노드를 큐에 넣지 않기위한 조건
            Node edgeNode = new Node(edgeIndex, me.cost+1); //큐에 넣기위한 Node를 생성한다
            edgeNode.edge = ar.get(edgeIndex).edge; //새로운 Node를 생성했기에 인접 노드도 함께 저장한다.
            pq.add(edgeNode);
        }
    }
    return maxCost;
}