728x90
반응형
11404 - 플로이드
https://www.acmicpc.net/problem/11404
문제
모든 도시 쌍 (a, b)에 대해 도시 a에서 b로 가는데 필요한 비용의 최솟값
입력
첫째 줄: 도시의 개수 n (2 <= n <= 100)
둘째 줄: 버스의 개수 m (1 <= m <= 100,000)
셋째 줄 ~ m+2줄: 버스의 정보
버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c
시작 도시와 도착 도시가 같은 경우 X, 비용 (자연수) <= 100,000
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음
출력
n개의 줄 출력
i번째 줄에 출력하는 j번째 숫자: 도시i에서 j로 가는데 필요한 최소 비용
만약, i에서 j로 갈 수 없는 경우 0 출력
풀이
플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)
모든 도시 쌍 (i, j) 간의 최소 이동 비용 구하기
- `map[i][j]`: 도시 i에서 j로 가는 최소 비용
- `i == j`: 자기 자신 => 0
- 나머지: 처음에는 도달할 수 X 상태 -> `INF`로 초기화
- `static final int INF = 1_000_000_000`
- -> `map[a][b] = Math.min(map[a][b], c)`
map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) map[i][j] = 0;
else map[i][j] = INF;
}
}
- 경유지 k, 출발지 i, 도착지 j
- i -> j (기존 경로) > i -> k -> j (최신 경로) => 갱신
- => 모든 도시 쌍 간 최단 경로
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][k] + map[k][j] < map[i][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
코드
import java.io.*;
import java.util.*;
// 플로이드
public class boj_11404 {
static int[][] map;
static final int INF = 1_000_000_000;;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) map[i][j] = 0;
else map[i][j] = INF;
}
}
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map[a][b] = Math.min(map[a][b], c);
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][k] + map[k][j] < map[i][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j] == INF) sb.append("0 ");
else sb.append(map[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}
11780 - 플로이드 2
https://www.acmicpc.net/problem/11780
문제
모든 도시 쌍 (a, b)에 대해 도시 a에서 b로 가는데 필요한 비용의 최솟값
입력
첫째 줄: 도시의 개수 n (2 <= n <= 100)
둘째 줄: 버스의 개수 m (1 <= m <= 100,000)
셋째 줄 ~ m+2줄: 버스의 정보
버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c
시작 도시와 도착 도시가 같은 경우 X, 비용 (자연수) <= 100,000
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음
출력
n개의 줄 출력
i번째 줄에 출력하는 j번째 숫자: 도시i에서 j로 가는데 필요한 최소 비용
만약, i에서 j로 갈 수 없는 경우 0 출력
nxn개의 줄을 출력
ixn+j번째 줄: 도시 i에서 j로 가는 최소 비용에 포함되어 있는 도시 개수 k 출력
도시 i에서 j로 가는 경로 출력 (공백)
이때, 도시 i와 j도 출력해야 함
만약, i에서 j로 갈 수 없는 경우 0 출력
풀이
for (int i = 1; i <= n; i++) {
Arrays.fill(dist[i], INF);
dist[i][i] = 0;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[i][k];
}
}
}
}
코드
import java.io.*;
import java.util.*;
// 플로이드 2
public class boj_11780 {
static final int INF = 1_000_000_000;;
static int[][] dist, path;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
dist = new int[n + 1][n + 1];
path = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
Arrays.fill(dist[i], INF);
dist[i][i] = 0;
}
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
if (c < dist[a][b]) {
dist[a][b] = c;
path[a][b] = b;
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[i][k];
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] == INF) sb.append("0 ");
else sb.append(dist[i][j]).append(" ");
}
sb.append("\n");
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] == INF || i == j) {
sb.append("0\n");
} else {
List<Integer> arr = new ArrayList<>();
int cur = i;
while (cur != j) {
arr.add(cur);
cur = path[cur][j];
}
arr.add(j);
sb.append(arr.size()).append(" ");
for (int city : arr) sb.append(city).append(" ");
sb.append("\n");
}
}
}
System.out.print(sb);
}
}
728x90
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[BOJ/] 백준 1197 - 최소 스패닝 트리 (Java) (0) | 2025.05.16 |
---|---|
[BOJ/] 백준 1260 - DFS와 BFS (Java) (0) | 2025.05.16 |
[BOJ/Greedy] 백준 1744 - 수 묶기 (Java) (0) | 2025.04.27 |
[BOJ/Greedy] 백준 11501 - 주식 (Java) (0) | 2025.04.27 |
[BOJ/Greedy] 백준 1541 - 잃어버린 괄호 (Java) (1) | 2025.04.27 |