🏆 알고리즘 문제 풀이
📌 문제 정보
- 문제명 : 특정한 최단경로
- 출처 : https://www.acmicpc.net/problem/1504
- 난이도 : G4
- 유형 : 다익스트라(Dijkstra), 최단 경로
🧐 문제 설명
방향 없는 그래프에서 1번 정점에서 N번 정점으로 가는 최단 경로를 구하는 문제.
단, 반드시 주어진 두 정점 v1, v2를 반드시 거쳐야 한다.
- 정점 개수: N (2 ≤ N ≤ 800)
- 간선 개수: E (0 ≤ E ≤ 200,000)
- 간선은 양방향, 가중치는 1,000 이하 자연수
👉 즉, 경로는 두 가지 경우만 고려하면 된다.
1 → v1 → v2 → N
1 → v2 → v1 → N
위 두 경로 중 더 짧은 것을 정답으로 출력하면 된다.
만약 경로가 불가능하다면 -1을 출력한다.
💡 접근 방법
-
다익스트라 3번 실행
1에서 시작하는 최단 거리v1에서 시작하는 최단 거리v2에서 시작하는 최단 거리
-
두 가지 경로 거리 계산
- case1 : 1 → v1 → v2 → N
- case2 : 1 → v2 → v1 → N
-
최솟값 출력
- 두 경우 모두 갈 수 없다면
-1출력
- 두 경우 모두 갈 수 없다면
📝 풀이 과정
| 단계 | 설명 |
|---|---|
| 1 | 그래프 입력 받기 (인접 리스트 활용) |
| 2 | 다익스트라 함수 구현 (우선순위 큐 사용) |
| 3 | 1, v1, v2에서 다익스트라 실행 |
| 4 | 두 가지 경우 거리 계산 |
| 5 | 가능한 경우 중 최솟값 출력, 불가능하면 -1 |
입력 & 출력 예시
🧑💻 코드
package Baekjoon;
import java.io.*;
import java.util.*;
public class B_1504_특정한최단경로 {
static int N, E;
static List<int[]>[] graph; // [정점, 가중치]
static final int INF = 1_000_000_000; // 충분히 큰 값
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
graph = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
// 간선 입력
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph[a].add(new int[]{b, c});
graph[b].add(new int[]{a, c}); // 양방향
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
// 다익스트라 3번 실행
int[] dist1 = dijkstra(1);
int[] distV1 = dijkstra(v1);
int[] distV2 = dijkstra(v2);
// 경우1: 1 → v1 → v2 → N
long case1 = (long) dist1[v1] + distV1[v2] + distV2[N];
// 경우2: 1 → v2 → v1 → N
long case2 = (long) dist1[v2] + distV2[v1] + distV1[N];
long ans = Math.min(case1, case2);
if (ans >= INF) System.out.println(-1);
else System.out.println(ans);
}
// 다익스트라
static int[] dijkstra(int start) {
int[] dist = new int[N + 1];
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.add(new int[]{start, 0}); // [정점, 거리]
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int now = cur[0];
int cost = cur[1];
if (cost > dist[now]) continue;
for (int[] next : graph[now]) {
int nextNode = next[0];
int nextCost = cost + next[1];
if (nextCost < dist[nextNode]) {
dist[nextNode] = nextCost;
pq.add(new int[]{nextNode, nextCost});
}
}
}
return dist;
}
}🔍코드해설
1️⃣ 거리 배열 초기화
int[] dist = new int[N + 1];
Arrays.fill(dist, INF); // 모든 거리를 무한대로 초기화
dist[start] = 0; // 시작 정점의 거리는 0👉 처음에는 모든 정점까지의 거리를 무한대(INF)로 설정하고, 시작 정점의 거리를 0으로 둔다.
2️⃣ 우선순위 큐(힙) 선언
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.add(new int[]{start, 0}); // [정점 번호, 현재까지의 거리]👉 PriorityQueue는 현재까지의 거리가 가장 짧은 정점을 우선적으로 꺼내기 위해 사용한다.
즉, 항상 가장 가까운 정점부터 탐색할 수 있게 해준다.
👉 여기서 Comparator.comparingInt(a -> a[1])는 큐 안의 요소를 두 번째 값, 즉 거리 기준으로 오름차순 정렬하겠다는 의미이다.
따라서 거리가 작은 정점이 큐에서 먼저 나오게 됩니다.
3️⃣ 큐에서 가장 가까운 정점 꺼내기
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int now = cur[0]; // 현재 정점
int cost = cur[1]; // 현재까지의 거리
if (cost > dist[now]) continue; // 이미 더 짧은 경로가 있으면 무시
👉 우선순위 큐에서 하나 꺼낸다.
이미 더 짧은 경로(dist[now])가 존재한다면 스킵한다.
4️⃣ 인접 노드 탐색
for (int[] next : graph[now]) {
int nextNode = next[0]; // 인접한 정점
int nextCost = cost + next[1]; // 현재 비용 + 간선 가중치
👉 현재 정점(now)에 연결된 인접 정점들을 확인한다.
그 정점까지 가는 새로운 거리(nextCost)를 계산한다.
5️⃣ 최단 거리 갱신
if (nextCost < dist[nextNode]) {
dist[nextNode] = nextCost; // 더 짧은 거리로 갱신
pq.add(new int[]{nextNode, nextCost}); // 큐에 삽입
}
}
}👉 만약 새로운 경로가 더 짧으면, dist[nextNode] 값을 갱신
pq에 다시 넣어서 나중에 탐색할 수 있도록 한다.
6️⃣ 결과 반환
return dist;👉 최종적으로 dist 배열에는 시작 정점에서 각 정점까지의 최단 거리가 저장된다.
💭 다익스트라 알고리즘
✨ 다익스트라 알고리즘이란?
다익스트라 알고리즘은 하나의 시작 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
간선의 가중치가 음수일 수 없다는 조건이 붙으며, 네트워크 경로 탐색이나 지도 서비스 등 다양한 분야에서 사용된다.
🛠️ 동작 원리
다익스트라는 기본적으로 가까운 정점부터 탐색하는 방식을 따른다.
- 시작 정점에서 각 정점까지의 거리를 저장한다. (처음에는 무한대, 시작 정점은 0)
- 방문하지 않은 정점 중 가장 가까운 정점을 선택한다.
- 그 정점을 거쳐 가는 경로를 확인하면서 더 짧은 경로가 있다면 갱신한다.
- 모든 정점을 방문할 때까지 2~3 과정을 반복한다.
📌 예시 과정
예를 들어, 시작 정점이 1번이고 다른 정점들과 연결된 그래프가 있다고 하자.
- 초기 거리 배열:
[0, ∞, ∞, ∞, ...] - 1번에서 가장 가까운 정점을 선택
- 선택한 정점을 통해 다른 정점들의 거리를 갱신
- 모든 정점을 방문할 때까지 반복
최종적으로 시작점에서 각 정점까지의 최단 거리가 구해진다.
📍 핵심 포인트
- 시작점에서 가까운 정점부터 탐색
- 우선순위 큐(힙)를 사용해 효율적인 구현
- 음수 간선이 없는 그래프에서만 사용 가능
