프로그래머스 가장 먼 노드

프로그래머스 가장 먼 노드

가장 먼 노드 Java

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

풀이

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

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

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

public static class Node implements Comparable { int index; int cost; ArrayList 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 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 ar, int n) { PriorityQueue 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; }

from http://webprogramcustom.tistory.com/58 by ccl(A) rewrite - 2021-09-05 17:26:06