이번주 알고리즘은 플로이드 워셜 알고리즘이다!
생전 처음 들어보는 알고리즘인데 다익스트라 친척인것 같다
플로이드 워셜
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘
다익스트라알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구함다익스트라알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면플로이드 워셜알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘 수행
한개의 정점인지 모든 정점인지에 따라 사용하는 알고리즘이 달라진다
정리
- 다익스트라에 비해 매우 짧아 구현이 쉬움
- 단계마다 '거쳐가는 정점'을 기준으로 알고리즘 수행 → 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요 없음
- 2차원 테이블에 최단 거리 정보 저장 (모든 지점에서 다른 모든 지점까지의 최단거리 저장)
DP알고리즘에 속함. 만약 노드의 개수가 N개라고 할 때, N번만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트 갱신 -다익스트라는 그리디 알고리즘에 속한다고 볼 수 있음- 시간 복잡도가
O(n^3)으로, 그래프의 크기가 작음
흠 이론만 봐서는 모르겠으니, 직접 문제를 풀면서 이해해보자
백준 12908번 : 텔레포트 3
문제
격자판 (x,y)
처음 수빈이 위치 (xs, ys) → 집 (xe, ye)
이동 방법
- 점프 : (x, y) → (x+1, y), (x-1, y), (x, y+1), (x, y-1) 4가지 방향 이동
- 텔레포트 : (x1, y1), (x2, y2)로 나타낼 수 있으며, 1 -> 2, 2 -> 1로만 텔포 가능, 10초 걸림
수빈이의 위치와 집의 위치가 주어졌을 때, 집에 가는 가장 빠른 시간은??
입력
xs ys - 수빈이의 위치
xe ye - 집의 위치
x1 y1 x2 y2 - 텔포 위치
x1 y1 x2 y2 - 텔포 위치
x1 y1 x2 y2 - 텔포 위치
출력
수빈이가 집에 가는 가장 빠른 시간
풀이
package baekjun.floydwarshall;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P12908 {
public static Node[] nodes;
public static long[][] distance;
public static int xs, ys, xe, ye;
public static int INF = Integer.MAX_VALUE;
public static class Node { // 각 좌표를 저장하는 Node 클래스
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
nodes = new Node[8]; // 노드 저장 배열
distance = new long[8][8]; // 플로이드 워셜 배열
xs = Integer.parseInt(st.nextToken()); // 시작 위치
ys = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
xe = Integer.parseInt(st.nextToken()); // 도착 위치
ye = Integer.parseInt(st.nextToken());
nodes[0] = new Node(xs, ys);
nodes[7] = new Node(xe, ye);
for (int i = 0; i < 8; i++) {
Arrays.fill(distance[i], INF); // 배열 초기화
}
distance[0][7] = distance[7][0] = Math.abs(xs - xe) + Math.abs(ys - ye); // 거리 계산
for (int i = 1; i < 7; i += 2) { // 텔레포트 입력 받기 - 2개씩 입력 들어와서 += 2
st = new StringTokenizer(br.readLine(), " ");
nodes[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 좌표 노드 저장
nodes[i + 1] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
distance[i][i + 1] = distance[i + 1][i] = Math.min(
Math.abs(nodes[i].x - nodes[i + 1].x) + Math.abs(nodes[i].y - nodes[i + 1].y), 10); // 텔포 10초 걸림
}
for (int i = 0; i < 8; i++) { // 반복하면서 거리 갱신
for (int j = 0; j < 8; j++) {
distance[i][j] = Math.min(distance[i][j], // 기존 거리와 비교해서 짧은거
Math.abs(nodes[i].x - nodes[j].x) + Math.abs(nodes[i].y - nodes[j].y));
}
}
for (int k = 0; k < 8; k++) {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]); // 중간 거리 비교
}
}
}
System.out.println(distance[0][7]);
}
}하 어렵다.....
어떻게 할지 모르겠어서 다른 분의 블로그를 봤다...
코드를 이해하는 것에 만족해야겠다...
일단 Node 클래스를 통해서 좌표값을 담아준다
배열이 8개인 이유는 시작위치, 텔레포트1~6, 종료위치 이렇게 총 8개의 좌표값이 필요해서 그렇다
처음 혼자 풀때는 모든 좌표를 다 넣어야 되는 줄 알고 문제의 상한값인 1,000,000,000 X 1,000,000,000의 배열을 만들려고 했는데 당연히 에러가 났다..
그냥 플로이드-워셜에 필요한 8개의 좌표값만 가지고 있으면 된다!
그리고 distance 배열은 8 X 8로 각 좌표간의 거리를 저장해 줄 배열이다
처음에 배열을 초기화 시켜주는데 INF는 모르는 값이라고 생각하면 된다
그리고 모든 거리를 계산 할 필요 없이 가지고 있는 좌표들의 거리만 계산해서 배열에 넣어준다
텔레포트는 10초가 소요되므로 만약 텔레포트 좌표 사이의 거리가 10보다 작다면 텔레포트를 하는게 손해라서 순수 거리를 배열에 넣어주고 그게 아니라면 10을 넣어주면 된다.
그 후에 반복하면서 거리값과 기존 좌표(텔포거리) 중에 작은것을 계산해서 넣어주고, 마지막으로 모든 배열을 돌면서 최소 거리를 업데이트 해주는 방식으로 진행하는 코드이다.
마지막에는 (0,7)의 좌표에 있는 값이 최소 거리이니 출력해주면 된다
한번 다른 사람의 코드를 보고 나니 어떤 방식으로 진행하는 지 알것 같아 추가적인 문제를 풀어봐야겠다.
