[백준 / BOJ] 11780 플로이드 2 (Java)

문제

출처 : https://www.acmicpc.net/problem/11780

11780번: 플로이드 2

n개의 도시와 n개의 도시를 연결하는 m개의 버스가 있을때, 각 도시를 오가기위해 지불해야하는 버스의 최소비용과 이때의 경로를 구하는 문제다.

---

풀이

푸는데 2일이나 걸린 문제다..

경로를 찾는과정에서 생각보다 어려움을 겪었는데, Java언어가 String을 이어붙이는 메커니즘상(Java는 String을 붙일경우 새로운 String객체를 생성한다.) 각 경로를 비교해가며 최단경로를 찾는방식을 사용하기 힘들었다. (재귀를 들어가며 최단경로를 찾았을때, 지금까지 이동한 경로를 기억해야하기때문)

여러가지 시도 결과, 플로이드 와샬을 이용해 최소비용 배열을 만들어주는 과정에서 2차원 parent배열을 사용해 최단경로를 함께 업데이트 해줬다.

 

아이디어는 다음과 같다.

아이디어 1. routes[from1][to1] = mid1 : from1에서 to1으로 가는경로에 mid1을 경유해서 가는게 최단경로이다.

아이디어 2. routes[from1][to1] 의 값이 0 이라면, from1에서 to1으로 바로 가는것이 최단경로이다. (단, costs[from1][to1]이 0보다 큼으로써 routes[from1][to1]의 경로가 항상 존재함이 증명되어야한다. 만일 costs[from1][to1]이 0이며, routes[from1][to1]이 0이라면 이는 경로가 없음을 뜻한다.)

 

예를 들어, 

조건 1. routes[from1][to1] = mid1 일때,

routes[from1][to2] = to1 이라고 가정하자. 이뜻은, from1에서 to2로 가는경로는 from1 -> to1 -> to2라는 뜻이고, 이는 조건 1 에 의해서, 다음과 같다고 볼 수 있다.

(from1 에서 to2로 가는 경로) : from1 -> mid1 -> to1 -> to2 

따라서, 위 경로를 그대로 routes배열로 표현한다면 다음과 같이 된다.

routes[from1][to2]의 경로는 "routes[from1][mid1] + routes[mid1][to1] + routes[to1][to2]";

(단, routes[from1][mid1] = 0, routes[mid1][to1] = 0, routes[to1][to2] = 0 이라고 가정하며 costs[from1][to2]가 0이 아니므로, 모두 경로가 있음이 보장된다)

routes[from][to] 가 0이라면 from -> to로 가는것이 최단경로 이므로 최종적으로 from1 -> to2의 최단경로는

from1 -> mid1 -> to1 -> to2가 된다.

 

이 아이디어를 그대로 구현하면된다.

 

주요 소스코드

 

	private void buildRoutePrinter(StringBuilder sb){
		StringBuilder tempBuilder = new StringBuilder();
		for(int i = 1; i <= this.city; i++){
			for(int j = 1; j <= this.city; j++){
				if(this.costs[i][j] == 0 || this.costs[i][j] == this.INF) sb.append(0);
				else {
					tempBuilder.setLength(0);
					int routeCount = this.buildRoutePrinter(i, j, tempBuilder) + 1;
					sb.append(routeCount).append(" ").append(tempBuilder).append(j);
				}
				sb.append("\n");
			}
		}
	}

	private int buildRoutePrinter(int from, int to, StringBuilder sb){
		if(this.routes[from][to] == 0){
			sb.append(from).append(" ");
			return 1;
		}
		return this.buildRoutePrinter(from, this.routes[from][to], sb) + this.buildRoutePrinter(this.routes[from][to], to, sb);
	}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/11780%20%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C%202/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃