[백준] 단계별로 풀어보기(단계:27, 동적 계획법과 최단거리 역추적,JAVA)11780번, 플로이드 2

문제 링크

11780번: 플로이드 2

 

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

위 문제는 출발지점에서 목적지점까지 가는 비용이 최소인 경로를 구하는 문제이기 때문에 최단경로 알고리즘을 사용하였습니다.

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

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

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

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

 

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

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

 

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

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

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

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

 

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

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

이 문제에 핵심은

1. 한 도시에서 다른 도시로 출발하는 버스이다. = 방향이 있는 간선이다.

2. 버스의 비용은 10만보다 작거나 같은 자연수이다.

3. 출발점에서 각 지점까지 최소비용, 방문 도시 개수, 경로를 출력해야 한다.

4. 출발 도시와 도착 도시도 방문 도시와 경로에 포함된다.

 

그래프에 대한 내용을 정의하기 위해 ArrayList<ArrayList<Integer>>의 형태로 리스트를 만들어주었습니다.

위와 같이 정의하여 데이터를 저장하면 각 정점이 어떤 정점으로 이동하는지 간단하게 저장할 수 있습니다.

예를 들어 

1 -> 4

1 -> 3

2 -> 5

3 -> 4

ArrayList<ArrayList<Integer>>의 저장되는 모습은 리스트 안에 리스트가 포함되는 형식으로 저장됩니다.

정점
1	3	4
2	5
3	1	4
4	1	4
5	2

그래프의 값을 리스트에 저장하였다면 출발점을 기준으로 for문을 이용하여 플로이드 알고리즘을 구현하였습니다.

 

플로이드 탐색하는 과정을 살펴보시려면 아래 링크 문제를 풀 때 어떻게 진행되는지 표현한 것을 참고해주시면 감사하겠습니다.

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

 

이 문제에서는 최단 비용뿐만 아니라 지나가는 도시의 경로를 출력해야 합니다.

 

버스를 타고 이동할 때 이전 도시에 값들을 저장하는 배열을 만들었습니다.

 

만약 도시1 -> 도시2로 이동한다면

next[1][2] = 1이 저장되는 형식입니다.

 

플로이드 알고리즘으로 최단 비용 경로를 구할 때 같이 배열을 구성합니다.

 

이후 경로를 출력할 때에는 LIFO(후입선출) 형식의 Stack을 이용하여 도착 지점부터 출발지점까지 가는 next에 값들을 역추적하면서 Stack에 도시 번호를 저장합니다.

 

Stack에 저장된 값들을 출력하여 경로를 표현할 수 있습니다.

 

Stack에 저장되었던 도시들은 최단 비용으로 갔을 때 들린 도시의 수로 표현할 수 있기 때문에 저장된 수만큼 결과로 출력하면 됩니다.

 

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

1. 입력값을 받아서 저장합니다.

2. 플로이드 알고리즘을 이용하여 각 지점에서 다른 지점에 최소 비용과 이동 경로를 배열에 저장합니다.

3. 최소 비용, 방문 도시 개수, Stack을 이용한 경로를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 버스의 이동경로를 나누어 graph에 저장하였습니다.
• 플로이드 알고리즘를 이용한 지점에서 다른 지점으로 가는 최단 비용과 경로를 구하는 cal함수를 실행하였습니다.
• BufferedWriter에 최단 비용을 저장하였습니다.
• Stack과 next[]을 이용하여 이동 경로와 방문 도시 개수를 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 플로이드 알고리즘을 이용하여 next와 arr를 구성합니다. 

import java.io.*;
import java.util.*;

public class Main {
	static int n,m,INF = 10000001;
	static int[][] arr,next;		//최단 경로, 이전 경로 저장하는 배열
    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
    	Stack<Integer> stack = new Stack<Integer>();
    	StringTokenizer st;
    	n = Integer.parseInt(br.readLine());
    	m = Integer.parseInt(br.readLine());
    	arr = new int[n+1][n+1];
    	next = new int[n+1][n+1];
        //최단 경로 저장할 배열 초기화
    	for(int i=1;i<=n;i++) {
    		for(int j=1;j<=n;j++) {
    			if(i!=j)
    				arr[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());
    		arr[a][b] = Math.min(arr[a][b], c);
    		next[a][b] = a;
    	}
    	cal();		//최단 비용과 경로 구하는 함수 실행
        //최단 비용 값들 BufferedWriter 저장
    	for(int i=1;i<=n;i++) {
    		for(int j=1;j<=n;j++) {
    			if(arr[i][j] ==INF)
    				bw.write("0 ");
    			else	
    				bw.write(arr[i][j] + " ");
    		}
    		bw.newLine();
    	}
    	//방문 도시 개수와 경로 BufferedWriter 저장
    	for(int i=1;i<=n;i++) {
    		for(int j=1;j<=n;j++) {
    			if(next[i][j]==0)		//해당 도시 도착하지 못할 경우
    				bw.write("0\n");
    			else {		//해당 도시 도착할 때
    				int e = j;
    				stack.add(e);
    				while(next[i][e] != i) {
    					stack.add(next[i][e]);
    					e = next[i][e];
    				}
    				bw.write(stack.size() + 1 + " ");
    				bw.write(i + " ");
    				while(!stack.isEmpty()) 
    					bw.write(stack.pop() + " ");
    				bw.newLine();
    			}
    		}
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //for문을 이용한 플로이드 알고리즘을 구현한 함수
    static void cal() {
    	for(int i=1;i<=n;i++) {
    		for(int j=1;j<=n;j++) {
    			for(int k=1;k<=n;k++) {
    				if(arr[j][k] > arr[j][i] + arr[i][k]) {
    					arr[j][k] = arr[j][i] + arr[i][k];	//최단 비용
    					next[j][k] = next[i][k];		// 이전 도시
    				}
    			}
    		}
    	}
    	return;
    }
}