이번 강좌에서는 취업용 알고리즘 시험에서 자주 등장하는 “최단 경로 구하기” 문제를 다룰 것입니다. 최단 경로 문제는 그래프 이론에서 중요한 주제로, 복잡한 네트워크 환경에서 최적의 경로를 찾아야 할 때 매우 유용합니다. 우리는 자바를 사용하여 이 문제를 해결하는 방법에 대해 논의할 것입니다.
문제 설명
다음의 조건을 만족하는 그래프가 주어질 때, 특정 출발점에서 특정 도착점까지의 최단 경로를 구하는 문제입니다.
- 그래프는 방향성이 있으며, 가중치가 부여된 간선을 가집니다.
- 노드의 총 개수는
V, 간선의 총 개수는E입니다. - 그래프의 노드는 1번부터
V번까지 번호가 매겨져 있습니다.
문제 예시
입력으로 다음과 같은 그래프가 주어질 때:
5 8 // 노드 5개, 간선 8개 1 2 2 // 1번 노드에서 2번 노드로 가는 가중치 2 1 3 3 // 1번 노드에서 3번 노드로 가는 가중치 3 2 3 1 // 2번 노드에서 3번 노드로 가는 가중치 1 2 4 1 // 2번 노드에서 4번 노드로 가는 가중치 1 3 4 6 // 3번 노드에서 4번 노드로 가는 가중치 6 3 5 1 // 3번 노드에서 5번 노드로 가는 가중치 1 4 5 2 // 4번 노드에서 5번 노드로 가는 가중치 2 1 5 10 // 1번 노드에서 5번 노드로 가는 가중치 10
출발점은 노드 1, 도착점은 노드 5일 때, 최단 경로의 가중치를 구하시오.
문제 분석
이 문제는 다익스트라 알고리즘을 통해 해결할 수 있습니다. 다익스트라 알고리즘은 주어진 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다음의 단계를 따릅니다:
- 시작 노드를 0으로 설정하고, 모든 다른 노드는 무한대로 설정합니다.
- 인접 노드의 거리를 업데이트합니다.
- 가장 거리가 짧은 노드를 선택하여 경로를 결정합니다.
- 이 과정을 모든 노드가 선택될 때까지 반복합니다.
알고리즘 구현
이제 다익스트라 알고리즘을 자바로 구현해보겠습니다.
import java.util.*;
public class DijkstraAlgorithm {
static class Edge {
int node;
int weight;
Edge(int node, int weight) {
this.node = node;
this.weight = weight;
}
}
static final int INF = Integer.MAX_VALUE;
static List> graph = new ArrayList<>();
static int[] dist;
static boolean[] visited;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int V = scanner.nextInt(); // 노드의 개수
int E = scanner.nextInt(); // 간선의 개수
// 그래프 초기화
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
}
// 간선 입력
for (int i = 0; i < E; i++) {
int from = scanner.nextInt();
int to = scanner.nextInt();
int weight = scanner.nextInt();
graph.get(from).add(new Edge(to, weight));
}
int start = 1; // 시작 노드
dist = new int[V + 1];
visited = new boolean[V + 1];
// 거리 초기화
Arrays.fill(dist, INF);
dist[start] = 0;
// 다익스트라 알고리즘 실행
dijkstra(start);
// 최단 거리 출력
int end = 5; // 도착 노드
System.out.println("최단 거리: " + dist[end]);
}
private static void dijkstra(int start) {
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
pq.offer(new Edge(start, 0));
while (!pq.isEmpty()) {
Edge current = pq.poll();
int currentNode = current.node;
if (visited[currentNode]) continue;
visited[currentNode] = true;
for (Edge edge : graph.get(currentNode)) {
if (dist[currentNode] + edge.weight < dist[edge.node]) {
dist[edge.node] = dist[currentNode] + edge.weight;
pq.offer(new Edge(edge.node, dist[edge.node]));
}
}
}
}
} 코드 설명
위 코드에서 DijkstraAlgorithm 클래스는 다익스트라 알고리즘을 구현합니다. 다음은 각 부분에 대한 설명입니다:
Edge클래스: 노드와 가중치를 저장하는 클래스입니다.graph: 그래프를 인접 리스트 형식으로 표현합니다.dist: 각 노드까지의 최단 거리 배열입니다.visited: 노드 방문 여부를 나타냅니다.dijkstra(): 다익스트라 알고리즘을 구현한 메소드입니다. 우선순위 큐를 사용하여 최단 거리를 업데이트합니다.
결과 및 실행
위의 코드를 실행하면, 입력으로 주어진 그래프에 대해 노드 1에서 노드 5까지의 최단 거리를 계산할 수 있습니다. 다음과 같은 결과가 나올 것입니다:
최단 거리: 3결론
이번 강좌에서는 자바를 사용하여 최단 경로 문제를 해결하는 방법을 살펴보았습니다. 다익스트라 알고리즘은 다양한 응용 프로그램에서 사용되며, 복잡한 그래프를 다룰 때 매우 유용합니다. 이 문제를 통해 그래프 이론의 기초적인 개념과 자바에서의 구현 방법을 익힐 수 있었습니다. 앞으로 더 어려운 알고리즘 문제들과 다양한 그래프 탐색 기법에 대해서도 알아보도록 하겠습니다.