문제
풀이
이 문제는 하나의 노드에서 다른 모든 노드까지의 최소 경로를 구하는 문제로 다익스트라 알고리즘을 이용해 풀이할 수 있다.
다익스트라 알고리즘
다익스트라 알고리즘은 아래와 같은 방식으로 동작한다.
- 출발 노드 설정
- 최단 거리 테이블 초기화
방문하지 않은 && 최단 거리가 가장 짧은노드를 선택- 3에서 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신
- 끝날 때 까지 3, 4번 과정을 반복
문제의 테스트 케이스에 적용
- 1번 노드부터 나머지 노드로의 최단 경로를 구하는 문제이므로 출발 노드는 1번으로 설정
- 간선에 가중치가 없으므로 출발노드와 이웃하는 노드까지의 거리를 1로 설정
- 방문하지 않은 노드 중 최단 경로가 최소인 2(또는 3)번 노드를 선택
- 이웃한 노드의 최단 경로를 갱신
- 방문하지 않은 노드 중 최단 경로가 최소인 3번 노드를 선택
- 이웃한 노드의 최단 경로를 갱신
이 과정을 끝까지 반복하면 아래와 같은 상태가 된다.
따라서 최단 경로가 최대인 노드의 개수는 3개이다.
그리디 알고리즘
다익스트라 알고리즘은 매 단계마다 최초 노드에서 경로가 최단인 노드를 선택하고 선택된 노드의 최단 경로를 그 시점에 확정하기 때문에 매 시점에 가장 최적의 해를 선택한다는 점에서 그리디 알고리즘에 속한다고 할 수 있다.
코드 (설명 포함)
import java.util.*;
class Solution {
// 우선순위 큐에서 사용하기 위한 Node 클래스
static class Node implements Comparable<Node>{
int index; // 현재 노드의 index
int currentDistance; // 현재 노드의 현재까지의 최단 경로
Node(int index, int currentDistance) {
this.index = index;
this.currentDistance = currentDistance;
}
// 우선순위 큐에서 대소 비교를 위해 Comparable 인터페이스를 구현해야 함
@Override
public int compareTo(Node other) {
return this.currentDistance - currentDistance;
}
}
public int solution(int n, int[][] edge) {
int[] distances = new int[n + 1]; // 매 시점 노드까지의 최단거리를 저장
Arrays.fill(distances, Integer.MAX_VALUE); // 최초엔 무한(도달 불가)으로 채우기
List<List<Integer>> graph = new ArrayList<>(); // 각 노드와 이웃한 노드 리스트를 저장
// graph 초기화
for (int i = 0 ; i <= n ; i++) {
graph.add(new ArrayList<>());
}
// 이웃 노드 정보 추가 (양방향)
for (int[] e : edge) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
// 다익스트라 알고리즘 시작
// 매 step에 가장 최단 경로가 짧은 노드를 선택하기 위해 반복문을 도는 대신 우선순위 큐를 사용
PriorityQueue<Node> queue = new PriorityQueue<>();
// 초기 (1번) 노드 설정
queue.offer(new Node(1, 0)); // Node(index, currentDistance)
distances[1] = 0;
while(!queue.isEmpty()) {
Node currentNode = queue.poll();
// 이전에 방문한 노드면 제외
// 우선순위 큐에서 빼온 currentDistance 값이 최단 경로 테이블에 기록된 최소 경로 값보다 크면
// 이미 방문한 노드이므로 처리할 필요 없음
if (currentNode.currentDistance > distances[currentNode.index]) {
continue;
}
// 연결된 노드들 갱신
for (int neighbor : graph.get(currentNode.index)) {
int newDistance = distances[currentNode.index] + 1;
// 새로운 경로가 더 짧을 경우에만 최단 경로 테이블 갱신 및 큐에 추가
if (newDistance < distances[neighbor]) {
distances[neighbor] = newDistance;
queue.offer(new Node(neighbor, newDistance));
}
}
}
// 최대 경로가 몇인지 탐색
int maxDistance = 0;
for (int i = 1 ; i <= n ; i++) {
maxDistance = Math.max(maxDistance, distances[i]);
}
// 최대 경로를 갖는 노드가 몇 개인지 탐색
int count = 0;
for (int distance : distances) {
if (distance == maxDistance) {
count++;
}
}
return count;
}
}