[백준] 단계별로 풀어보기(단계:25, 최단 경로,JAVA)1956번, 운동

문제 링크

1956번: 운동

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

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

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

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

 

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

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

 

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

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

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

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

 

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

 

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

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

 

이 문제에 핵심은

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

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

3. 자기 자신으로 돌아오는 싸이클이 존재하면 최단 싸이클을 출력한다.

4. 싸이클이 존재하지 않는다면 -1을 출력한다.

 

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

 

정점이 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,2)... 형태의 값들을 0으로 초기화하지 않고 INF으로 초기화를 해주어야 합니다.

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

 

 

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

 

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

	1	2	3
1	INF	1	5
2	INF	INF	2
3	INF	1	INF

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

 

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

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

 

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

 

현재 최단 거리 = INF

정점 1을 거쳐서 갈 때

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

 

정점 2을 거쳐서 갈 때

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

 

정점 3을 거쳐서 갈 때

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

 

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

 

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

현재 최단 거리 = INF

 

정점 1을 지날 때

 

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

 

정점 2을 거쳐서 갈 때

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

 

정점 3을 거쳐서 갈 때

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

 

현재 최단 거리 INF보다 작은 값이 존재하기 때문에 distance[2][2]는 3으로 변경합니다.

 

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

	1	2	3
1	INF	1	3
2	INF	3	2
3	INF	1	3

 

표를 통해 각 정점에서 다른 정점에 최단 거리를 확인할 수 있습니다.

 

결과로 싸이클이 존재하면 가장 작은 값을 출력해야 하기 때문에

(1, 1), (2, 2), (3, 3)의 값을 확인하였을 때 INF가 아닌 값이 있으면 싸이클이 존재한다고 판단할 수 있습니다.

(2, 2)와 (3, 3)의 값이 INF가 아니기 때문에 둘 중 더 작은 값을 결과로 출력하면 됩니다.

(2, 2)와 (3, 3)의 값은 같기 때문에 싸이클이 존재하며 가장 작은 값인 3을 결과로 출력합니다.

 

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

1. 최단 거리를 저장하는 배열을 INF로 초기화해줍니다.(싸이클이 존재하는지 확인하기 위해!)

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

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

4. 플로이드 워셜 알고리즘이 끝난 뒤 싸이클이 존재하는지 확인합니다.

5. 싸이클이 존재하지 않으면 -1, 싸이클이 존재하면 최단 싸이클을 결과로 출력합니다.

 

※저는 INF를 Integer.MAX_VALUE/2로 설정하였습니다.

 

 

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

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

 

import java.io.*;
import java.util.*;
public class Main{
	public static int V,E,INF = Integer.MAX_VALUE/2;
	public static int[][] 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 = new StringTokenizer(br.readLine()," ");
    	V = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	distance = new int[V+1][V+1];
    	for(int i=1;i<=V;i++) 	//최단 거리 값 모두 INF로 초기화
        	Arrays.fill(distance[i], INF);

    	for(int i=0;i<E;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		int c = Integer.parseInt(st.nextToken());
    		distance[a][b] = c;	//입력값 관련 최단거리 설정
    	}
    	shortestPath();	//플로이드 워셜 알고리즘 수행
    	
    	int result = INF;	//싸이클 존재하는지 확인하기 위해 INF로 초기화
    	for(int i=1;i<=V;i++) 	//싸이클 값중 가장 작은 값 가져오기
    		result = Math.min(result, distance[i][i]);
    	
    	if(result==INF)	//가장 작은 값이 INF이면 싸이클 존재하지 않는다.
    		bw.write("-1\n");
    	else
    		bw.write(result + "\n");	//가장 작은 싸이클 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //플로이드 워셜 알고리즘 수행하는 함수
    public static void shortestPath() {
    	for(int i=1;i<=V;i++) {
    		for(int j=1;j<=V;j++) {
    			for(int s=1;s<=V;s++) {
    				if(distance[j][s] > distance[j][i] + distance[i][s])
    					distance[j][s] = distance[j][i] + distance[i][s];
    			}
    		}
    	}
    }
}