Kakao 2021 Blind Test - Lv3. 합승 택시 요금 (Java)

문제 요약

A, B 두 사람이 출발점(s)에서 출발해 각각의 도착 지점까지 택시를 탄다고 할 때, 최저 예상 택시요금을 계산

 

[문제 설명]

1. A와 B가 출발지에서 도착지까지 택시를 탄다.
2. A와 B는 어느 특정 지점까지 합승할 수 있다.
3. 합승한 지점에서 내린 후 각자의 도착지까지 따로 택시를 탄다.
4. 합승하여 도착지까지 가는 것이 최소 비용인가? 따로 택시를 타서 도착지까지 가는 것이 최소 비용인가?

[생각의 과정]

• 처음에 합승하여 도착지까지 가는 것과  // 따로 택시를 타서 도착지까지 도착하는 비용(합승하지 않는 경우)을 구분하여 생각하려 하였습니다.
• 그러나 어느 지점까지 합승하였는지를 답하는 곳은 없습니다. 
• 이는 출발점에서 모든 지점까지의 최소 요금을 구한 뒤 임의의 합승 지점을 선택하여 또 다른 모든 지점까지의 최소 비용을 더해줘도 된다는 뜻입니다. 
• 즉, 문제의 핵심은 각 지점에서 다른 지점으로의  '최소 비용'을 구할 수 있는지의 여부였습니다.
• 최소 비용을 구하는 방법에는 다익스트라와 플로이드 와샬이 대표적입니다.
• 지점의 개수가 200이기 때문에 200 * 200 * 200을 하여도 1억을 넘지 않아 플로이드 와샬로 접근하였습니다.

---

✔︎ 다익스트라로 접근한다면 어떨까요?

• 다익스트라로 접근한다고 가정해봅시다.
• 만약 모든 지점들이 연결되어있다면 자기 자신을 제외한 모든 지점을 고려하여 최소 비용을 계산하여야 합니다.
• 더불어 출발지를 기존 출발점뿐 아닌, 합승한 도착점부터 다른 지점으로까지의 최소 비용을 구하여야 합니다. 
• 모든 지점을 출발지로 다른 지점들까지의 최소 비용을 구하여 많은 경우의 수 중 전체 최소 비용을 적은 값을 찾아내어야 한다는 뜻입니다.
• 시간 복잡도를 줄이기 위하여 Priority Queue를 이용하여 최소 비용을 계산한다 가정해 봅시다.
• 다익스트라의 시간 복잡도가 O(ElogV)이고, 
• 하나의 지점에서 다른 지점까지의 최소 비용과 합승한 곳까지 고려하여 시간 복잡도를 계산해보자면, (19900 log 200)
• (19900 log 200) * (198 (출발지와 도착지를 제외한, 합승하여 도착한 곳의 후보 개수)) = 3,940,200 * log 200 = 9,066,518.38892입니다.
• 다익스트라로 풀어도 괜찮지만, 계산 횟수를 줄이기 위하여 정렬 등의 아이디어를 생각해내어야 합니다.

---

제약 조건

• 지점의 개수 n (3 이상 200 이하)
• 출발지 s, A의 도착지 a, B의 도착지 b (1 이상 n 이하의 자연수, 각기 서로 다른 값)
• fares: 2차원 정수 배열 (fares의 개수는 1 이상 최대 경로의 수인 n * (n-1) / 2 이하)
  • 출발지, 도착지, 요금 ( 1이상 100,000 이하 )
  • 무방향 그래프

n	s	a	b	fares	result
6	4	6	2	[[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]]	82

---

문제 접근 :  플로이드 와샬 (경유지 - 출발지 - 도착지)

// 22.06.01 2021 카카오 블라인드 - 합승 택시 요금

public class Solution {

    public static void main(String[] args) {
        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(6, 4, 6, 2, fares));
    }

    public static int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE; // 최저 예상 택시 요금 

    // 1. 그래프 만들기 (출발점이 1부터 시작한다) - 출발지부터 도착지까지의 비용
        int[][] graph = new int[n + 1][n + 1];

		// 그래프 초기화 (그래프가 가진 값이 출발지부터 도착지까지의 비용이므로 0으로 초기화된 값 변경 필요)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j)
                    graph[i][j] = 100000 * (n-1) + 1; // 자기 자신을 제외한 모든 지역을 다 거쳐왔을 때의 합 + 1
            }
        }

	// 출발지부터 도착지까지의 요금
        for (int i = 0, length = fares.length; i < length; i++) {
            int start = fares[i][0];
            int end = fares[i][1];
            int fare = fares[i][2];

            // 무방향 그래프
            graph[start][end] = fare;
            graph[end][start] = fare;
        }

    // 2. 모든 정점에서 다른 정점까지의 최소 비용 구하기 (플로이드 와샬)
        for (int k = 1; k <= n; k++) { // 경유지
            for (int i = 1; i <= n; i++) { // 출발지
                if (i == k) continue;
                for (int j = 1; j <= n; j++) { // 도착지
                    if (i == j || j == k) continue;
                    graph[i][j] = graph[i][j] > graph[i][k] + graph[k][j] ? graph[i][k] + graph[k][j] : graph[i][j];
                }
            }
        }

    // 3. 비용 구하기 (합승한 경우와 합승하지 않은 모든 경우를 고려)
        for (int i = 1; i <= n; i++) { // i : 같이 합승한 지점, 1인경우 합승을 하지 않은 경우
            int cost = graph[s][i] + graph[i][a] + graph[i][b];
            if (answer > cost) // answer가 가진 택시 요금보다 적을 경우 갱신
                answer = cost;
        }
        return answer;
    }
}

---

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/72413

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