[Programmers] LV3. 합승 택시 요금

https://programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

 

✔ 문제 조건

1. n개의 지점 (1번~n번)
2. 간선은 두 지점 사이의 거리 (택시요금), 양방향 그래프
3. A와 B는 합승 가능하다. i번째 지점까지 합승했다면 총 비용은 A,B가 i번째 지점까지 합승했을 때 비용 + i에서 A, B 지점까지 각각 발생하는 비용의 합이다.
4. 합승하지 않았을 때 비용이 더 저렴하다면 합승하지 않아도 된다.
5. A, B가 S에서 각자의 도착 지점까지 택시를 타고 갈 때 발생하는 최저 예상 택시 요금을 구하시오

✔ 접근 과정

1. 플루이드 워샬 알고리즘으로, 각 지점 간의 최소 이동 비용을 구한다.
2. 합승하지 않았을 때의 최소 비용을 구한다: S->A + S->B
3. 합승했을 때의 최소 비용을 구한다.
   1~N번 정점을 각각 경유하여 가는 경우: S->경유지 + 경유지->A + 경유지->B
4. 2번 비용과 3번 비용 중 최소 비용을 구하여 리턴한다.

✔ 주의할 점

1. 합승하지 않았을 때의 비용을 따로 구해야 한다고 생각했지만 플루이드 워샬 알고리즘을 위해 가중치 인접 행렬 전체를 구하기 때문에 따로 구하지 않아도 되었다.
2. 플루이드 워샬 알고리즘을 위해 인접 행렬을 최대값으로 초기화 하기 때문에 연산 오류가 발생한다. 경유 했을 경우를 위해 최대값 끼리 더했을 때 정수 범위를 넘어가서 음수로 표기되기 때문이다. 해결법은 다음과 같다.
   1. 연산 오류가 발생하지 않는 최대값을 설정한다.
      요금 f의 최대값은 100,000이고, 지점 개수의 최대값은 200이다. 모든 지점을 경유했을 때의 최대값은 200 * 100,000이다. 따라서 최대값을 200 * 100,000+1으로 초기화하면 최대값끼리 더해도 정수 범위 내이기 때문에 연산 오류가 나지 않는다.
   2. 최대값 끼리 연산하는 경우를 없앤다.
      연산 오류가 발생하는 부분은, 1) 플루이드 워샬 알고리즘 내에서 어떤 지점을 경유했을 때의 비용이 더 적은지를 살펴볼 때 2) 최종 답을 구하기 위해 각 정점을 경유하여 가는 경유의 비용을 살펴볼 때 두 부분이다.
      이때 adjMatrix[i][j]==INF라면 i, j는 인접하지 않은 경우기 때문에 살펴볼 필요가 없다. 따라서 continue로 처리한다.
3. 인접행렬에서 adjMatrix[S][S]==0이기 때문에 접근 과정의 2번을 굳이 실행하지 않아도, 합승하지 않았을 때의 요금이 3번에서 구해지지만 코드 가독성을 위해 추가했다. 어차피 min값을 초기화하긴 해야하니까..
   

   

import java.util.*;
// 210514

class Solution_LV3_합승택시요금 {
	
	public static void main(String[] args) {
		int n = 6, s = 4, a = 6, b = 2;
		int[][] fares = new int[][] {
			{4, 1, 10}, 
			{3, 5, 24}, 
			{5, 6, 2}, 
			{3, 1, 41},
			{5, 1, 24}, 
			{4, 6, 50}, 
			{2, 4, 66}, 
			{2, 3, 22}, 
			{1, 6, 25}
		};
		System.out.println(solution(n, s, a, b, fares));
	}
	
    static public int solution(int n, int s, int a, int b, int[][] fares) {   
        // 1. 모든 정점들 사이의 인접 행렬 만들기 & 양방향 그래프
        int INF = 987654321;
//    	int INF = 100000 * 200 + 1;
        int[][] adjMatrix = new int[n+1][n+1];
        for(int i=0; i<=n; i++) {
        	Arrays.fill(adjMatrix[i], INF);
        	adjMatrix[i][i] = 0;
        }
        for(int[] fare: fares) {
        	int from = fare[0], to = fare[1], cost = fare[2];
        	adjMatrix[from][to] = cost;
        	adjMatrix[to][from] = cost;
        }
        
        // 2. 플루이드 워샬 알고리즘 : 경, 출, 도
        for(int k=1; k<=n; k++) {
        	for(int i=1; i<=n; i++) {
        		if(k==i) continue;
        		for(int j=1; j<=n; j++) {
        			if(k==j || i==j) continue;
        			if(adjMatrix[i][k]==INF || adjMatrix[k][j]==INF) continue;
        			if(adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j]) {
        				adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
        			}
        		} 
        	}
        }
        
        // 3. 합승하지 않고 바로 가는 경우: S->A + S->B
        int min = adjMatrix[s][a] + adjMatrix[s][b]; 
        // INF로 초기화 해도 상관없음 adhMatrix[S][S]는 0이기 때문에 합승하지 않는 경우가 4번에서도 구해짐
        
        // 4. 1~N번 정점을 각각 경유하여 가는 경우: S->경유지 + 경유지->A + 경유지->B
        for(int i=1; i<=n; i++) {
        	if(adjMatrix[s][i]==INF || adjMatrix[i][a]==INF || adjMatrix[i][b]==INF) continue;
        	min = Math.min(min, adjMatrix[s][i] + adjMatrix[i][a] + adjMatrix[i][b]);
        }
        
        return min;
    }
}

 

* 우선순위큐와 다익스트라로 최단 거리 구하는 방법

https://velog.io/@hyunjkluz/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A472413-%ED%95%A9%EC%8A%B9-%ED%83%9D%EC%8B%9C-%EC%9A%94%EA%B8%88Java