[Floyd-Warshall] 플로이드 워셜 알고리즘 기본 코드 형식

플로이드 워셜 알고리즘 기본 코드 형식

플로이드 워셜 알고리즘 구현을 위해 알아두어야 할 코드 템플릿

- 코딩테스트와 같은 문제 해결을 위해서는 구현력이 매우 중요

- 알고리즘에 대한 이해와 더불어 알고리즘 구현을 위한 기본적인 코드 템플릿을 익혀야 함

- 기본 코드 템플릿을 토대로 각 문제의 조건에 맞추어 답 코드를 구현

 

플로이드 워셜 알고리즘 중요 표인트!

- 플로이드 워셜 유형의 경우 3중 for문 구현이 핵심

- 백준 11404번 플로이드 문제 참고(기본적인 플로이드 유형 알고리즘 문제)

백준 11404번 플로이드 (JAVA)

- INF 값 설정

• INF란 무한대(infinite) 값, 비용이 무한대 값이란 건 경로가 없다는 의미
• INF 값 설정 시 문제 내에서 가능한 최대거리보다 큰 값으로 해야 함
• 이 때 다익스트라처럼 Integer.MAX_VALUE를 사용하면 오버플로우가 발생할 수 있기 때문에 주의 필요

public class 플로이드워셜_기본 {
    private static int N, M;
    private static final int INF = 100 * 100000 + 1; // 경로가 없을 경우
    private static int[][] dist; // 거리 비용

    public static void main(String[] args) {
        dist = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dist[i], INF); 
            //시작점과 도착점이 다른 경우는 무한대로 초기화(INF) 
            //비용이 무한대 값이란 건 경로가 없다는 의미
            
            dist[i][i] = 0; 
            // 시작점과 도착점이 같은 경우는 없으니까 0 으로 초기화
        }
        
       // ... 입력 값 받는 코드 구현 ...
        
        floyd();
    }

    private static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    //i에서 j로 바로 가는 비용과 i에서 k를 거쳐 j로 가는 비용을 비교
                }
            }
        }
    }