코딩테스트 준비를 위해선 다양한 알고리즘 문제를 풀어보는 것이 중요합니다. 이번 강좌에서는 ‘최소 비용 구하기’ 문제를 다뤄보겠습니다. 이 문제는 그래프 이론과 동적 프로그래밍(Dynamic Programming) 기술을 필요로 합니다. 여러분의 프로그래밍 능력을 한층 더 강화해 줄 것입니다.
문제 설명
주어진 방향 그래프에서 여러 개의 노드와 간선이 있습니다. 각 간선은 특정 비용을 가지고 있습니다. 우리는 한 노드에서 시작하여 다른 노드로 이동할 때 드는 최소 비용을 구해야 합니다. 노드는 여러 개가 있을 수 있으며, 어떤 두 노드 사이에는 여러 개의 경로가 존재할 수 있습니다.
입력
- 첫 번째 줄엔 노드의 개수 N과 간선의 개수 M이 주어진다 (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000)
- 다음 M개의 줄엔 간선 정보가 주어진다. 각 간선은
u v c의 형식으로 주어지며, 이는 노드 u에서 v로 가는 간선의 비용이 c임을 뜻한다. (1 ≤ c ≤ 1000) - 마지막 줄엔 시작 노드 S와 목표 노드 T가 주어진다.
출력
시작 노드 S에서 목표 노드 T로 가는 최소 비용을 출력하라. 만약 도달할 수 없다면 -1을 출력한다.
문제 예시
입력:
5 6
1 2 2
1 3 3
2 3 1
2 4 4
3 4 1
4 5 1
1 5
출력:
6
알고리즘 아이디어
이 문제는 그래프에서 최단 경로를 찾는 문제와 유사합니다. 다익스트라(Dijkstra) 알고리즘을 사용하여 효율적으로 문제를 해결할 수 있습니다. 이 알고리즘은 한 노드에서 다른 노드로의 최단 경로를 찾는데 최적화되어 있습니다. 우리는 이 알고리즘을 사용하여 시작 노드에서 목표 노드까지의 최소 비용을 추적합니다.
다익스트라 알고리즘 설명
다익스트라 알고리즘은 다음과 같은 방식으로 작동합니다:
- 우선, 시작 노드에서 각 노드까지의 거리를 무한대로 초기화하되 시작 노드의 거리는 0으로 초기화합니다.
- 우선순위 큐를 사용하여 현재 최소 비용으로 접근할 수 있는 노드를 선택합니다.
- 선택한 노드의 인접한 노드에 대해 비용을 갱신합니다. 만약 새로운 경로가 더 나은 비용이라면 해당 노드를 업데이트하고 큐에 추가합니다.
- 목표 노드에 도달할 때까지 이 과정을 반복합니다. 모든 노드를 처리한 이후 목표 노드의 최종 거리를 반환합니다.
자바 코드 구현
import java.util.*;
public class MinCostPath {
static class Edge {
int to, cost;
Edge(int to, int cost) {
this.to = to;
this.cost = cost;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 노드 수
int M = sc.nextInt(); // 간선 수
List> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int c = sc.nextInt();
graph.get(u).add(new Edge(v, c));
}
int S = sc.nextInt(); // 시작 노드
int T = sc.nextInt(); // 목표 노드
System.out.println(dijkstra(N, graph, S, T));
}
static int dijkstra(int n, List> graph, int start, int target) {
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.cost));
pq.add(new Edge(start, 0));
while (!pq.isEmpty()) {
Edge current = pq.poll();
if (current.to == target) {
return dist[target];
}
for (Edge edge : graph.get(current.to)) {
if (dist[current.to] + edge.cost < dist[edge.to]) {
dist[edge.to] = dist[current.to] + edge.cost;
pq.add(new Edge(edge.to, dist[edge.to]));
}
}
}
return -1; // 도달할 수 없는 경우
}
}
코드 설명
위 코드에서:
- 우선 노드 수(N)와 간선 수(M)를 입력받습니다.
- 각 간선에 대한 정보를 입력받고 그래프를 인접 리스트 형태로 저장합니다.
- 다익스트라 알고리즘을 위한 초기화 작업을 진행합니다. 거리 배열(dist)을 생성하고 시작 노드의 거리를 0으로 설정합니다.
- 우선순위 큐를 사용하여 현재 노드의 인접 노드에 대한 최단 경로를 갱신하며 반복합니다.
- 목표 노드에 도달하면 그 거리를 반환하고, 도달할 수 없는 경우 -1을 반환합니다.
최적화와 주의사항
다익스트라 알고리즘은 모든 간선의 가중치가 0 이상일 때 유효합니다. 만약 음수 간선이 있을 경우 벨만 포드 알고리즘을 고려해야 합니다. 또한, 성능 최적화를 위해 우선순위 큐를 사용할 때는 최소 힙을 사용하는 것이 좋습니다.
결론
이번 강좌에서는 ‘최소 비용 구하기’ 문제를 통해 다익스트라 알고리즘을 학습했습니다. 알고리즘 문제를 해결하는 연습을 통해 코딩테스트에 대한 자신감을 얻고, 문제 해결 능력을 더욱 향상시킬 수 있기를 바랍니다. 다음 시간에는 더 다양한 알고리즘을 소개하겠습니다.