[알고리즘-이론] 플로이드 와샬

eunseon·2021년 9월 3일
0

알고리즘

목록 보기
1/1

📑 목차


❓플로이드 와샬 정의

💁🏻‍♀️ 플로이드 와샬 과정

✨ 문제에 적용해보기


우선, 이 블로그를 보며 공부했던 내용을 정리한 글이라는 점을 말씀드립니다! 🙂

나동빈 - 플로이드 와샬

❓플로이드와샬 정의

→ '거쳐가는 정점'을 기준으로 최단 거리를 구하는 알고리즘입니다.

그렇다면, 다익스트라와는 어떤 점이 다를까요?

다익스트라 vs 플로이드 와샬의 차이점

다익스트라 : 하나의 정점에서 출발했을 때에 다른 모든 정점으로의 최단 경로를 구하는 알고리즘, 모든 정점에서 출발했을 때를 보는 알고리즘

플로이드 와샬 : '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶을 때 사용하는 알고리즘입니다. '거쳐가는 정점'을 기준인 점이 가장 다릅니다.

💁🏻‍♀️ 플로이드 와샬 과정

  1. 예시로, 가중치를 가진 유향 그래프가 이렇게 있다고 생각해봅시다.

  1. 1의 사진에서 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열로 나타내면 아래 사진과 같습니다.

    아래 사진은 '현재 계산된 최소 비용'인데 이 상태에서 플로이드 와샬을 통하여 거쳐가는 정점을 기준으로 최단 거리를 구할 것 입니다 🙂

3. 이때, X에서 Y로 가는 최소 비용 vs X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용을 비교하면 됩니다.

3-1. 1를 거쳐서 가는 경우가 더 빠른 경우가 존재한다면 빠른 경우로 최소 비용을 계산하면 됩니다.

D[2,4]의 값은 D[2,4] vs (D[2,1] + D[1,4]) 중에서 더 작은 값으로 교체됩니다.

무한 vs 15가 되므로 15로 갱신됩니다.

  1. 노드 2를 거치는 경우
  1. 이렇게 3, 4까지 계산하여 갱신하면 최단 거리가 나오게 됩니다.

수정해야할 부분이 있거나 보완해야하는 사항이 있다면 언제든지 말씀해주세요!

✏️ 플로이드 와샬을 사용할 수 있는 알고리즘 문제들

11403번: 경로 찾기

11404번: 플로이드

9205번: 맥주 마시면서 걸어가기

코딩테스트 연습 - 합승 택시 요금

✨ 문제에 적용해보기

이 중, 경로 찾기라는 문제에 플로이드 와샬을 적용해봅시다.

경로 찾기 문제는 무향그래프에서 갈 수 있는 경로가 있다면 1로 변경, 아니라면 0으로 두는 문제입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_11403_경로찾기 {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());

		int arr[][] = new int[N + 1][N + 1];
		int d[][] = 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++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				d[i][j] = arr[i][j];
			}
		}
		
//이 부분이 플로이드 와샬의 핵심 부분 :) 
		//k=거쳐가는 노드  
		for(int k = 1; k<=N; k++) {
			//i=출발 노드 
			for(int i=1; i<=N; i++) {
				//j=도착하는 노드 
				for(int j = 1; j<=N;j++) {
					if(d[i][k]+d[k][j]>1&&d[i][j]==0) {
						d[i][j] = 1; 
					}
				}
			}
		}
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
		     System.out.print(d[i][j]+" ");
			}
			System.out.println();
		}

	}// end of main

}// end of class

이렇게 배열을 입력받아 노드의 갯수만큼 for문(플로이드 와샬)을 해주었더니 풀린 문제였습니다 🙂

📕 Reference

나동빈 - 플로이드 와샬

0개의 댓글