[백준] 단계별로 풀어보기(단계:25, 최단 경로,JAVA)11404번, 플로이드

문제 링크

11404번: 플로이드

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

최단경로는 시작 정점에서 목표 정점까지 최소의 비용으로 갈 수 있는 경로를 구하는 것입니다.

최단 경로를 구하는 알고리즘은 대표적으로 3개가 존재합니다.

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

3. 플로이드 워셜 알고리즘

 

3가지 알고리즘은 문제를 해결할 때 사용하는 알고리즘만 설명하도록 하겠습니다.

정점을 연결하는 노선이 여러개인 경면 플로이드 워셜 알고리즘으로 구현합니다.

 

플로이드 워셜 알고리즘이란?

1. 각 정점들을 기준으로 n번을 거쳐서 각 정점들을 도착하는 최단 거리를 구합니다.

2. 이동을 할 때마다 이동한 거리가 현재 저장된 거리보다 작으면 변경합니다.

3. 위 과정을 반복이 끝나면 각 정점에서 다른 정점에 최단 거리를 구할 수 있습니다.

 

글로는 잘 설명하지 못한 것 같아서 아래에 예제 문제를 풀면서 어떻게 진행되는지 자세히 보여드리겠습니다.

 

더 자세한 내용은 아래 링크를 통해 확인해주시기 바랍니다.

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 입력값으로 주는 내용은 모두 그래프의 내용입니다.

2. 방향성이 있는 간선이다.

3. 동일한 정점의 방향으로 비용만 다른 경우가 존재한다.

4. 각 정점이 다른 정점에 도착하지 못한다면 0을 출력합니다.

 

저는 반복문을 통해 플로이드 워셜 알고리즘을 구현하여 해결하였습니다.

 

정점이 5개일 때 각 정점이 다른 정점으로 가는 최단 거리를 보여주는 표의 초기화를 보여드리면

( 0 = 자기 자신은 이동하지 않음, INF = 현재 도착하는지 확인 불가능)

	1	2	3	4	5
1	0	INF	INF	INF	INF
2	INF	0	INF	INF	INF
3	INF	INF	0	INF	INF
4	INF	INF	INF	0	INF
5	INF	INF	INF	INF	0

 

그래프의 값을 받으면 정점끼리 이동거리를 최단 거리로 저장한 뒤 플로이드 워셜 알고리즘을 실행하여 각 정점이 다른 정점들의 최단 거리를 구하도록 합니다.

예제입력 1에서 그래프의 값을 받았을 때 표는

	1	2	3	4	5
1	0	2	3	1	10
2	INF	0	INF	2	INF
3	8	INF	0	1	1
4	INF	INF	INF	0	3
5	7	4	INF	INF	0

그래프의 값을 최단 거리로 적용하였다면 각 정점을 기준으로 플로이드 워셜 알고리즘을 구현하였습니다.

 

예제 입력1의 대하여 살펴보겠습니다.

아래는 예제로 주어진 그래프입니다.

 

플로이드-워셜로 정점 1에서 정점 2으로 다른 정점을 거쳐서 갈 때를 확인해보겠습니다.

 

현재 최단 거리 = 2

정점 1을 거쳐서 갈 때

거리 = distance[1][1] + distance[1][2] = 0 + 2 = 2

 

정점 2을 거쳐서 갈 때

거리 = distance[1][2] + distance[2][2] = 2 + 0 = 2

 

정점 3을 거쳐서 갈 때

거리 = distance[1][3] + distance[3][2] = 3 + INF = INF

 

정점 4을 거쳐서 갈 때

거리 = distance[1][4] + distance[4][2] = 1 + INF = INF

 

정점 5을 거쳐서 갈 때 

거리 = distance[1][5] + distnace[5][2] = 10 + 4 = 14

 

현재 최단 거리 2보다 작은 값이 존재하지 않기 때문에 distance[1][2]는 2로 유지합니다.

 

정점 1에서 정점 5으로 다른 정점을 거쳐서 갈 때에는

현재 최단 거리 = 10

 

정점 1을 지날 때

 

거리 = distance[1][1] + distance[1][5] = 0 + 10 = 10

 

정점 2을 거쳐서 갈 때

거리 = distance[1][2] + distance[2][5] = 2 + INF = INF

 

정점 3을 거쳐서 갈 때

거리 = distance[1][3] + distance[3][5] = 3 + 1 = 4

 

정점 4을 거쳐서 갈 때

거리 = distance[1][4] + distance[4][5] = 1 + 3 = 4

 

정점 5을 거쳐서 갈 때 

거리 = distance[1][5] + distnace[5][5] = 10 + 0 = 10

 

현재 최단 거리 10보다 작은 값이 존재하기 때문에 distance[1][5]는 4로 변경합니다.

 

위 과정을 모두 반복하고 나면 표는

	1	2	3	4	5
1	0	2	3	1	4
2	12	0	15	2	5
3	8	5	0	1	1
4	10	7	13	0	3
5	7	4	10	6	0

 

표를 통해 각 정점에서 다른 정점에 최단 거리를 확인할 수 있으므로

표의 값들을 결과로 출력하면 됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 최단 거리를 저장하는 배열을 0과 INF로 초기화해줍니다.

2. 그래프의 입력값에 따라 최단 거리 저장하는 배열도 변화시켜줍니다.

3. 플로이드 워셜 알고리즘을 수행하여 각 정점이 다른 정점에 가는 최단 거리를 구합니다.

4. 플로이드 워셜 알고리즘이 끝난 뒤 최단 거리가 저장된 배열을 결과로 출력합니다.

 

※저는 INF를 Integer.MAX_VALUE로 설정하였기 때문에 최단 거리 저장 배열을 long형으로 선언해주었습니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 그래프에 대한 정보 분리하였습니다.
• 반복문으로 최단 경로(플로이드 워셜)를 구하는 shortestPath 함수를 만들었습니다.
• 각 정점에서 다른 정점으로 가는 최단 경로를 구하였습니다.
• BufferedWriter에 최단 경로가 저장된 배열의 내용을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• shortestPath은 distance[][]를 통해 인접한 정점을 탐색하였습니다.
• shortestPath는 플로이드-워셜 알고리즘과 반복문을 이용하여 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int n,m;	//정점 수, 간선 수
	public static long[][] distance;	//최단 거리 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //------입력값 저장 및 배열 초기화--------
    	StringTokenizer st;
    	n = Integer.parseInt(br.readLine());
    	m = Integer.parseInt(br.readLine());
    	distance = new long[n+1][n+1];
    	for(int i=1;i<=n;i++) {
    		for(int j=1;j<=n;j++) {
    			if(i==j)
    				distance[i][j] = 0;
    			else
    				distance[i][j] = Integer.MAX_VALUE;
    		}
    	}
        //그래프 값 최단거리 배열에 적용
    	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());
    		
            //비용만 다른 간선이 존재하기 때문에 Math.min을 통해 최소값을 구함
    		distance[a][b] = Math.min(distance[a][b], c);
    	}
    	
    	shortestPath();		//플로이드-워셜 알고리즘 실행
    	
        //최단 거리 배열에 대한 내용 BufferedWriter 저장
    	for(int i=1;i<=n;i++) {
    		for(int j=1;j<=n;j++) {
    			if(distance[i][j]==Integer.MAX_VALUE)
    				bw.write("0 " );
    			else
    				bw.write(distance[i][j] + " ");
    		}
    		bw.newLine();
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //반복문으로 플로이드-워셜 알고리즘 구현한 함수
    public static void shortestPath() {
    	for(int i=1;i<=n;i++) {		//거쳐가는 정점
    		for(int j=1;j<=n;j++) {		//출발 정점
    			for(int s=1;s<=n;s++) {		//도착 정점
    				distance[j][s] = Math.min(distance[j][s], distance[j][i] + distance[i][s]);
    			}
    		}
    	}
    	return;
    }
}