[BOJ_11404] 플로이드 (골드 4) - JAVA

 

11404번: 플로이드

 

---

🐾 알고리즘

• 그래프에서 최단경로를 구하는 알고리즘에는 세가지가 있다.
  • 다익스트라
  • 플로이드-워샬
  • 벨만포드
• 플로이드-워샬 : 모든 노드간에 최단거리를 탐색한다. 그렇기 때문에 시작점이 존재하지 않는데, 다른 알고리즘 문제에 비해 노드개수의 범위가 적다. 
  • 삼중 포문을 돌리는 것이 핵심 포인트인데, 중간 거점(K)에 대해서 먼저 반복문을 실행시켜줘야 한다. 

 

---

🐾 생각 포인트

• 개인적으로 처음 공부해본 이론 중 다익스트라보다는 쉽게 풀이할 수 있었다.
• 특히 삼중 포문 돌리는 것에 대해서도 생각해봤는데, 중간 거점을 거쳐가면서 최단거리를 계산하려면 어쩔 수 없이 K에 대해 먼저 반복문을 실행하는 것이 맞는 것 같다.
• 아래 문제 같은 경우는 Int 범위를 넘어가기 때문에 INF (무한대 ) 를 설정할 때 Integer.MAX_VALUE로 선언해주면 안된다는 것을 유의해야한다.

 

---

🐾 소스코드

package hijpa;

import java.io.*;
import java.util.*;
public class Main {
    static int N, M;
    static int[][] dist;
    static final int INF = 100000001;
    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+1;i++){
            for(int j=1;j<N+1;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 a = Integer.parseInt(st.nextToken()); //시작
            int b = Integer.parseInt(st.nextToken()); //끝
            int c = Integer.parseInt(st.nextToken()); //비용

            dist[a][b] = Math.min(dist[a][b], c);
        }

        for(int k=1;k<N+1;k++){
            for(int i=1;i<N+1;i++){
                for(int j=1;j<N+1;j++){
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        for(int i=1;i<N+1;i++){
            for(int j=1;j<N+1;j++){
                if(dist[i][j] == INF){
                    System.out.print("0 ");
                }else{
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }


}

---

😵‍💫 공부해야 할 점

• 다익스트라도 소홀히 하지말자..
• 코테 단골 다익스트라.
• 처음보는 알고리즘들도 많이 접해보자!!