플로이드-워셜 알고리즘
✏️dp(동적계획법)의 개념을 활용한 최단경로 탐색 알고리즘
✏️ 벨만포드 알고리즘과 마찬가지로 음수 가중치 에지가 있어도 수행이 가능하다.
✏️ 시간복잡도는 O(V^3)으로 느린편이다. 반복문을 노드 개수 V만큼 총 3번 반복하기 때문.
우선 동적계획법의 원리부터 간단히 적어본다.
노드가 1~4까지 4개 있다고 가정했을 때, 1부터 4까지 가는 최단경로가 1→2→4 라고 하자.
이는 1부터 2까지 가는 최단경로와 2부터 4까지 더하는 최단경로의 조합이 된다. Min(1→2) + Min( 2→4)
플로이드 워셜 알고리즘은 이와 유사하게 최단거리를 저장하는 배열을 만들고 dp 원리를 이용하여 값을 업데이트 해준다.
이 배열을 D라고 했을 때 D[Start][End]는 Start에서 End로 가는 최단 거리를 뜻한다.
그렇다면 플로이드 워셜 알고리즘의 배열 업데이트 조건을 알 수 있다.
Start에서 End로 갈 때 들리는 경유지를 K라고 할 때, Math.min( D[Start][End], D[Start][K] + D[K][End])
백준 11403 경로찾기
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int dist[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
dist = new int[n+1][n+1];
//인접행렬에 받은 데이터 그대로 저장해
for(int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= n; j++) {
dist[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int k = 1; k <= n; k++) { //k는 경유하는 지점
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(dist[i][k] == 1 && dist[k][j] == 1)
dist[i][j] = 1;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
System.out.printf(dist[i][j] + " ");
}
System.out.println();
}
}
}
백준 1389 케빈 베이컨의 6단계 법칙
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻
www.acmicpc.net
package baekjoon;
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int dist[][];
static final int INF = 10000001;
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());
m = Integer.parseInt(st.nextToken());
dist = new int[n+1][n+1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i==j) dist[i][j] = 0; //대각선 자기자신은 0
else dist[i][j] = INF;
}
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
dist[s][e] = 1; //관계가 있는 경우 1로
dist[e][s] = 1; //양방향
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(dist[i][j] > dist[i][k] + dist[k][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
int ans = 0;
int minV = Integer.MAX_VALUE;
for(int i = 1; i <= n; i++) {
int sum = 0;
for(int j = 1; j <= n; j++) {
sum += dist[i][j];
}
if(sum < minV) {
minV = sum;
ans = i;
}
}
System.out.println(ans);
}
}
백준 11404 플로이드
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
😓INF 값을 Integer.MAX_VALUE로 설정하는 것보다 문제에 비용은 100,000보다 작거나 같은 자연수이다 라는 조건이 있으므로 10000001으로 설정해주었다.
😓이상하게 BufferedWriter를 사용하면 IDE에서는 잘 풀리지만 백준에 제출하면 틀렸다고 뜬다. System.out.print로 리팩토링하니 통과되었다. 왜그러지 . .
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int dist[][];
static final int INF = 10000001;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
dist = new int[n+1][n+1];
//인접행렬 초기화
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) dist[i][j] = 0;
else dist[i][j] = INF;
}
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if(dist[s][e] > v) dist[s][e] = v; //더 작은 값으로
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(dist[i][j] > dist[i][k]+dist[k][j])
dist[i][j] = dist[i][k]+dist[k][j];
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(dist[i][j] == INF)
System.out.printf("0 ");
else
System.out.printf(dist[i][j]+ " ");
}
System.out.println();
}
}
}
'Algorithms > study log' 카테고리의 다른 글
[java] 트리와 DFS (0) | 2024.02.26 |
---|---|
[java] 큐 / 우선순위 큐 / 힙 (0) | 2024.02.23 |
[java] 벨만포드 알고리즘 (0) | 2024.02.06 |
[java] 다익스트라 알고리즘 (0) | 2024.02.01 |
[백준 나무자르기] 이분탐색시 시작 혹은 끝 지점 설정하는 방법 (0) | 2024.01.17 |