b11780. 플로이드 2

 

https://www.acmicpc.net/problem/11780

 

 

 

📌 자바(Java)로 푸는 플로이드 2 - 백준 11780 🛣️

최단 거리 + 경로 출력까지 포함한 플로이드 워셜(Floyd-Warshall)

 

🔎 문제 개요

 

백준 11780 - 플로이드 2는

모든 도시 쌍에 대해 최단 경로의 거리를 구하는 것뿐만 아니라,

각 최단 경로를 직접 경로로 출력하는 문제입니다.

 

---

 

💡 예제 입력

5
14
1 2 2
1 3 3
1 4 1
...

 

💡 예제 출력

0 2 3 1 10
0
2 1 2
3 1 3
2 1 4
...

 

 

---

🛠 알고리즘 접근 방식

 

이 문제는 전형적인 Floyd-Warshall (플로이드-워셜) 알고리즘에

✔ 경로 추적까지 덧붙이는 구조입니다.

 

• costs[i][j]: 도시 i에서 j까지의 최소 비용
• lists[i][j]: 도시 i에서 j까지 이동할 때 거쳐야 하는 경유 도시 리스트

 

---

🔹 Java 코드 설명

📌 초기화

costs = new int[N+1][N+1];
lists = new ArrayList[N+1][N+1];

✔ costs[i][j]를 INF로 초기화하며

✔ 경로 저장용 lists[i][j]는 각 쌍마다 ArrayList 생성

 

📌 간선 입력

costs[a][b] = Math.min(cost, costs[a][b]);

✔ 동일 노선 중 더 짧은 비용만 저장

 

📌 플로이드 워셜 핵심

if (costs[i][j] > costs[i][k] + costs[k][j]) {
    costs[i][j] = costs[i][k] + costs[k][j];
    routeTracking(i, j, k);
}

✔ i → j로 바로 가는 것보다

✔ i → k → j가 더 저렴하다면 갱신

✔ 이 때 경로 리스트도 업데이트

 

📌 경로 갱신 함수

public static void routeTracking(int i, int j, int k){
    lists[i][j].clear();
    lists[i][j].addAll(lists[i][k]);
    lists[i][j].add(k);
    lists[i][j].addAll(lists[k][j]);
}

✔ 중간에 k를 거친 경로로 전체 경로 업데이트

✔ 재귀가 아닌 플랫한 리스트 구조 유지

 

📌 출력

▶ 거리 출력

if (costs[i][j] == INF) sb.append(0 + " ");
else sb.append(costs[i][j] + " ");

 

▶ 경로 출력

int size = lists[i][j].size();
sb.append((size + 2) + " " + i + " ");
for (int num : lists[i][j]) sb.append(num + " ");
sb.append(j + "\n");

✔ 경로 출력은

 

• 시작 도시 i
• 경유지들
• 도착 도시 j
• 까지 모두 포함

---

🏆 정리

✅ 핵심 포인트

• Floyd-Warshall 기본 구조는 O(N³)
• 경로 저장은 중간 경유지를 리스트로 누적
• 경로 출력이 필요할 때는 리스트를 직접 복사 + 연결